Hi,
I am trying to solve TEMPLEQ (http://www.spoj.pl/problems/TEMPLEQ/) using Interval Trees. However, I get WA.
The approach is pretty straightforward.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LEN 1000100
int val[LEN*3],p;
int N,Q;
int pilgrims;
int query(int i, int from, int to)
{
if(pilgrims > val[i]) return 0;
if(from == to)
return (val[i]>=pilgrims);
int m = (from+to)>>1,i2=i<<1;
return query(i2,from,m)+query(i2+1,1+(m),to);
}
void insert(int i, int pos, int from, int to, int inc=1)
{
if(pos > to || pos < from)
return;
if(pos == from && to == pos)
{ val[i]+=inc; return; }
int m = (from+to)>>1,i2=i<<1;
insert(i2,pos,from,m,inc);
insert(i2+1,pos,1+(m),to,inc);
val[i]=val[i2]+val[i2+1];
}
int threshold;
void remove_p(int i, int from, int to)
{
if(val[i]<threshold) return;
if(from==to && val[i]>=threshold)
{ val[i]--; return; }
int m = (from+to)>>1,i2=i<<1;
remove_p(i2,from,m);
remove_p(i2+1,1+(m),to);
val[i]=val[i2]+val[i2+1];
}
int main()
{
scanf("%d%d",&N,&Q);
memset(val,0,sizeof(val));
for(int i=0;i<N;i++)
{
int x;
scanf("%d",&x);
insert(1,i,0,N-1,x);
}
for(int i = 0; i < Q; i++)
{
int command, op;
scanf("%d%d",&command,&op);
if(command == 1)
{
op--;
insert(1,op,0,N-1);
}
else if(command == 2)
{
pilgrims = op;
printf("%d\n",query(1,0,N-1));
}
else if(command == 3)
{
threshold = op;
remove_p(1,0,N-1);
}
}
}
I prune superfluous calls by checking if case of query whether the total number of people in all the queues in the current range is less than the threshold, if yes, we do not go further in that branch.