求助!答案对了,为什么洛谷测全WA了?
查看原帖
求助!答案对了,为什么洛谷测全WA了?
100461
赤城舰长_cpp楼主2021/2/5 13:46

我在洛谷上交了程序

全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;
}
2021/2/5 13:46
加载中...