OJ-Problems-Source/HDOJ/4031_autoAC.cpp

83 lines
1.7 KiB
C++
Raw Permalink Normal View History

#include <iostream>
#include <string.h>
using namespace std;
const int MAX = 20000 + 100;
int C[MAX];
int N;
struct Node
{
int l;
int r;
};
int LowBit(int x)
{
return x & (-x);
}
void Update(int num,int key)
{
while(num <= N)
{
C[num] += key;
num += LowBit(num);
}
}
int CalSum(int num)
{
int sum = 0;
while(num > 0)
{
sum += C[num];
num -= LowBit(num);
}
return sum;
}
int main()
{
int T;
cin>>T;
int Case = 0;
while(T--)
{
int Q;
int CD;
int time = 0;
int used_time[MAX] = {0};
int porected[MAX] = {0};
Node attack[MAX] = {0};
memset(C,0,sizeof(C));
Case++;
cout<<"Case "<<Case<<":"<<endl;
scanf("%d%d%d",&N,&Q,&CD);
int i;
for(i=0;i<Q;i++)
{
char str[20];
scanf("%s",str);
if(str[0] == 'A')
{
scanf("%d%d",&attack[time].l,&attack[time].r);
Update(attack[time].l,1);
Update(attack[time].r+1,-1);
time++;
}
else
{
int num;
scanf("%d",&num);
int i;
for(i = used_time[num] ; i< time ;i++)
{
if(attack[i].l <=num && num <= attack[i].r )
{
porected[num]++;
used_time[num] = i + CD;
i = i + CD - 1;
}
}
printf("%d\n",CalSum(num)-porected[num]);
}
}
}
return 0;
}