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();
}