Skip to content

Instantly share code, notes, and snippets.

@edwardmjm

edwardmjm/Prob_A Secret

Created Aug 28, 2014
Embed
What would you like to do?
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=20005;
const int PP=150;
const int INF=1000000000;
int Tc,n,Q,per,m;
int CC;
int Time[N];
int Sum[N];
char Str[105];
int Tr[N];
struct Node{
int F[55];
int pre[55];
int T;
int l,r;
void push_down(){
bool flag=false;
for (int i=0;i<=per;i++)
if (F[i]){
flag=true;
break;
}
if (flag)
for (int i=l;i<=r;i++){
int c=T-Time[i];
if (c>per) c=per;
Time[i]=pre[c];
Sum[i]+=F[c];
}
T=CC;
for (int i=0;i<=per;i++){
F[i]=0;
pre[i]=CC-i;
}
}
}S[PP];
void Build(){
for (int i=1;i<=n;i++){
if (i==1 || i%PP==0)
S[i/PP].l=i;
S[i/PP].r=i;
S[i/PP].T=-INF;
}
m=n/PP;
for (int i=0;i<=m;i++){
for (int j=0;j<=per;j++){
S[i].F[j]=0;
S[i].pre[j]=S[i].T-j;
}
}
}
void Simple(int l,int r){
for (int i=l;i<=r;i++)
if (CC-Time[i]>=per){
Time[i]=CC;
Sum[i]++;
}
}
void Add(int i,int x){
for (;i<=n;i+=i&-i) Tr[i]+=x;
}
int Get_Sum(int i){
int ret=0;
for (;i;i-=i&-i) ret+=Tr[i];
return ret;
}
void Gao1(){
++CC;
int l,r;
scanf("%d%d",&l,&r);
Add(l,1);
Add(r+1,-1);
if (l/PP==r/PP){
S[l/PP].push_down();
Simple(l,r);
return;
}
int St=l/PP; if (l==S[St].l) St--;
int Ed=r/PP; if (r==S[Ed].r) Ed++;
for (int i=St+1;i<Ed;i++){
for (int j=0;j<=per;j++)
if (CC-S[i].pre[j]>=per){
S[i].pre[j]=CC;
S[i].F[j]++;
}
}
if (St>=0 && S[St].r>=l){
S[St].push_down();
Simple(l,S[St].r);
}
if (Ed<=m && S[Ed].l<=r){
S[Ed].push_down();
Simple(S[Ed].l,r);
}
}
void Gao2(){
int p;
scanf("%d",&p);
S[p/PP].push_down();
printf("%d\n",Get_Sum(p)-Sum[p]);
}
int main(){
scanf("%d",&Tc);
for (int k=1;k<=Tc;k++){
printf("Case %d:\n",k);
scanf("%d%d%d",&n,&Q,&per);
for (int i=1;i<=n;i++) { Time[i]=-INF; Sum[i]=0; Tr[i]=0; }
Build();
CC=0;
for (int i=0;i<Q;i++){
scanf("%s",Str);
if (Str[0]=='A')
Gao1();
else
Gao2();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment