我在洛谷上交了程序
全WA
下载了数据,都是却发现数据手工测试是对的
在我训练队的网站上也是AC的
然后洛谷还是爆了!?
请问各位大佬,这是为什么???
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<vector>
using namespace std;
const int N=1e6;
int n,Min;
int rt;
int tot,t;
int sum;
int ans;
struct treap
{
int l,r;
int pos,vis;
int num,size;
int cnt;
int father;
#define lc(k) tr[k].l
#define rc(k) tr[k].r
#define p(k) tr[k].pos
#define v(k) tr[k].vis
#define num(k) tr[k].num
#define s(k) tr[k].size
#define c(k) tr[k].cnt
#define fa(k) tr[k].father
}tr[N];
inline int read()
{
int num=0,sign=1;
char x;
while( (x=getchar())<'0' || x>'9' )
if(x=='-') sign=-1;
num=x-'0';
while( (x=getchar())>='0' && x<='9' )
num=num*10+x-'0';
return sign*num;
}
int minn(const int &aa,const int &bb)
{
return aa<bb? aa:bb;
}
void update(const int &k)
{
s(k)=s(lc(k))+s(rc(k))+num(k);
return;
}
void zig(int &x)
{
int y=lc(x);
lc(x)=rc(y);
rc(y)=x;
s(y)=s(x);
update(x);
x=y;
}
void zag(int &x)
{
int y=rc(x);
rc(x)=lc(y);
lc(y)=x;
s(y)=s(x);
update(x);
x=y;
}
void insert(int &k,const int &key,const int f)
{
if(!k)
{
k=++t;
num(k)=s(k)=1;fa(k)=f;
v(k)=key;p(k)=rand();c(k)=sum;
return;
}
else s(k)++;
if(v(k)+sum-c(k)==key){num(k)++;return;}
if(v(k)+sum-c(k)>key)
{
insert(lc(k),key,k);
if(p(lc(k))<p(k)) zig(k);
}
else
{
insert(rc(k),key,k);
if(p(rc(k))<p(k)) zag(k);
}
update(k);
return;
}
void dele(int &k)
{
if(!k) return;
dele(lc(k));
if(!lc(k))
{
if(v(k)+sum-c(k)<Min)
{
tot-=num(k);ans+=num(k);
k=rc(k);
dele(k);
}
}
update(k);
return;
}
int querykth(int k)
{
int x=rt;
while(x)
{
if(s(lc(x))<k && s(lc(x))+num(x)>=k) return v(x)+sum-c(x);
if(s(lc(x))>=k) x=lc(x);
else
{
k-=s(lc(x))+num(x);
x=rc(x);
}
}
return 0;
}
int main()
{
//freopen("test8.in","r",stdin);
//freopen("test8.out","w",stdout);
n=read();Min=read();
while(n--)
{
char p=getchar();
switch(p)
{
case 'I':
{
int x=read();
if(x<Min) continue;
tot++;
insert(rt,x,0);
break;
}
case 'A':
{
int x=read();
sum+=x;
break;
}
case 'S':
{
int x=read();
sum-=x;
dele(rt);
break;
}
case 'F':
{
int x=read();
if(x>tot) {printf("-1\n");continue;}
printf("%d\n",querykth(tot-x+1));
}
}
}
cout<<ans;
return 0;
}