ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1028. Stars

0.031s 312KB C++ sulotion
Posted by panhantao 16 Dec 2011 14:52
I've been stuck in this problem for a very long time, but today I got the idea of Binary Indexed Tree from wikipedia and finally solved this problem :)
Binary Indexed Tree,or BIT, can be viewed as a simplified version of Segment Tree,easier to code and less function to perform. But It's enough to solve this problem

#include<iostream>
#include<cstdio>
using namespace std;

const int Max = 32005;

int n;
int c[Max] = {0};
int level[Max] = {0};

int lowbit(int x)
{
    return x&(-x);
}

int sum(int i)
{
    int s = 0;
    while(i > 0)
    {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

void update(int pos,int val)
{
    while(pos <= Max)
    {
        c[pos] += val;
        pos += lowbit(pos);
    }
}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x ++;
        level[ sum(x) ] ++;
        update(x,1);
    }

    for(int i = 0; i < n; i ++)    printf("%d\n",level[i]);
}
Re: 0.031s 312KB C++ sulotion
Posted by vlyubin 9 Apr 2012 07:16
How can this even be correct if you don't use the y-coordinates at all?
Re: 0.031s 312KB C++ sulotion
Posted by Abzal 10 Jul 2012 00:54
Because in statement there was written that y-coordinates are already sorted
Re: 0.031s 312KB C++ sulotion
Posted by sysu2012zzp 18 Nov 2012 11:47
in function main,why you use "x ++"?
Re: 0.031s 312KB C++ sulotion
Posted by qulinxao 10 Jun 2013 10:58
cose in problem x in [0,32000 ]

so 0 is bad value for binary :)

so we just shift all x on some const ( just 1) so all value between 1 and power(2,someN)
Re: 0.031s 312KB C++ sulotion
Posted by Vitaly Grebennik 28 Nov 2019 03:40
Why do you use 32005 as a size of an array?