CVJETICI - Cvjetici

Tác giả: hieult

Ngôn ngữ: C++

#include <cstdio>
//#include <conio.h>

struct t_plant
{
       int left,right;
};

int plants;
t_plant plant[100100];
int minleft,maxright;

void enter()
{
     int p;
     scanf("%d",&plants);
     minleft = 200000; maxright = 0;
     for( p = 0;p<plants;p++)
     {
          scanf("%d %d",&plant[p].left,&plant[p].right);
          if(plant[p].left<minleft) minleft = plant[p].left;
          if(plant[p].right>maxright) maxright = plant[p].right;
     }
     maxright -= minleft;
     for(p = 0;p<plants;p++)
     {
           plant[p].left -= minleft;
           plant[p].right -= minleft;
     }
}

int norm,count[270000];

void init_counts()
{
     for(norm = 1;norm<=maxright;norm*=2);
}

int count_flowers(int pos)
{
    int p;
    int result = 0;
    for(p = norm+pos;p>0;p/=2) result+= count[p];
    count[norm+pos] -= result;
    return result;
}

void add_bar(int from,int to,int root,int width)
{
     if((from==0) &&(to == width-1)) count[root]++;
     else if(to<width/2) add_bar(from,to,2*root,width/2);
     else if(from>= width/2) add_bar(from-width/2,to-width/2,2*root+1,width/2);
     else
     {
         add_bar(from,width/2-1,2*root,width/2);
         add_bar(0,to-width/2,2*root+1,width/2);
     }
}

void grow_plants()
{
     int p,flowers;
     init_counts();
     for(p=0;p<plants;p++)
     {
         flowers = count_flowers(plant[p].left)+count_flowers(plant[p].right);
         printf("%d\n",flowers);
         if(plant[p].right> plant[p].left+1) add_bar(plant[p].left+1,plant[p].right-1,1,norm);
     }
}

int main()
{
    //freopen("CVJETICI.in","r",stdin);
    enter();
    grow_plants();
    //getch();
}

Download