求助!本机和在线IDE过,提交WA
查看原帖
求助!本机和在线IDE过,提交WA
42082
YZHX楼主2020/6/12 17:29

换了个机子和账号还是本机过提交wa

之前就有一次这种情况

大佬们能告诉我为啥吗QvQ

即使把输出-1那句话注释掉,也还是这样

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define db double
#define get getchar()
#define in inline
#define ls(x) a[x].ch[0]
#define rs(x) a[x].ch[1]
in int read ()
{
    int t=0; char ch=get;
    while (ch<'0' || ch>'9') ch=get;
    while (ch<='9' && ch>='0') t=t*10+ch-'0', ch=get;
    return t;
}
const int _=2e5+2;
const int inf=0x3f3f3f3f;
struct SPLAY{
    int ch[2],siz,w,cnt,ff,lazy;
}a[_];
int n,lim,root,tot;
#define check(x,y) (a[y].ch[1]==x)
in void pushdown(int x)
{
    a[ls(x)].lazy+=a[x].lazy;
    a[ls(x)].w+=a[x].lazy;
    a[rs(x)].lazy+=a[x].lazy;
    a[rs(x)].w+=a[x].lazy;
    a[x].lazy=0;
}
in void pushup(int x)
{
    a[x].siz=a[x].cnt+a[ls(x)].siz+a[rs(x)].siz;
}
in void rotate(int x)
{
    int y=a[x].ff;
    int z=a[y].ff;
    int k=check(x,y);
    pushdown(y),pushdown(x);
    a[z].ch[check(y,z)]=x;
    a[x].ff=z;
    a[y].ch[k]=a[x].ch[!k];
    a[y].ff=x;
    a[a[x].ch[!k]].ff=y;
    a[x].ch[!k]=y;
    pushup(y),pushup(x);
}
in void Splay(int x,int d)
{
    while(a[x].ff!=d)
    {
	int y=a[x].ff;
	int z=a[y].ff;
	if(z!=d)
	    (check(x,y) ^ check(y,z) ? rotate(x) : rotate(y));
	rotate(x);
    }
    if(d==0) root=x;
}

in void insert(int x)
{
    int k=root,ff=0;
    while(a[k].w!=x && k) {pushdown(k);ff=k,k=a[k].ch[a[k].w<x];}
    if(k) a[k].cnt++,a[k].siz++;
    else
    {
	k=++tot;
	if(ff) a[ff].ch[a[ff].w<x]=k;
	a[k].ff=ff;
	a[k].siz=a[k].cnt=1;
	a[k].w=x;
    }
    Splay(k,0);
}
in void find(int x)
{
    int k=root;
    while(!k) return;
    while(a[k].ch[a[k].w<x] && x!=a[k].w) k=a[k].ch[a[k].w<x];
    Splay(k,0);
}
in int kth(int x)
{
    int k=root;
    while(1)
    {
	pushdown(k);
	if(a[ls(k)].siz>=x) k=ls(k);
	else if(a[ls(k)].siz+a[k].cnt>=x) return a[k].w;
	else x=x-a[ls(k)].siz-a[k].cnt,k=rs(k);
    }
}
int main()
{
    n=read(),lim=read();
    insert(-inf),insert(inf);
    int ans=0;
    for(re int i=1;i<=n;i++)
    {
	char ch;
	scanf("%ch",&ch);
	int k=read();
	if(ch=='I')
	{
	    if(k<lim) continue;
	    insert(k);
	    continue;
	}
	if(ch=='A')
	{
	    a[root].lazy+=k,a[root].w+=k;
	    continue;
	}
	if(ch=='S')
	{
	    find(k+lim);
	    int qwe=root;
	    if(a[qwe].w-k<lim)
	    {
		a[rs(root)].ff=0,ans+=a[root].cnt+a[ls(root)].siz,root=rs(root);
	    }
	    else
	    {
		ans+=a[ls(root)].siz;
		a[root].siz-=a[ls(root)].siz;
		a[root].ch[0]=0;
	    }
	    a[root].lazy-=k;
	    a[root].w-=k;
	    continue;
	}
	if(ch=='F')
	{
	    if(k+1>a[root].siz) cout<<"-1"<<endl;
	    else printf("%d\n",kth(a[root].siz-k));
	}
    }
    cout<<ans-1<<endl;
}
2020/6/12 17:29
加载中...