QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#790733#7787. Maximum Ratingzhilin#WA 2ms11888kbC++142.0kb2024-11-28 15:03:342024-11-28 15:03:34

Judging History

你现在查看的是最新测评结果

  • [2024-11-28 15:03:34]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11888kb
  • [2024-11-28 15:03:34]
  • 提交

answer

#include<bits/stdc++.h>
#define ls(x) T[x][0]
#define rs(x) T[x][1]
#define maxn 1000005
using namespace std;
long long qread(){
	long long s=0,fu=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')fu=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		s=(s<<1)+(s<<3)+ch-'0';
		ch=getchar();
	}
	return s*fu;
}
long long val[maxn],pri[maxn],siz[maxn],sum[maxn];
int T[maxn][2];
int tot;
void pushup(int x){
	siz[x]=siz[ls(x)]+siz[rs(x)]+1;
	sum[x]=sum[ls(x)]+sum[rs(x)]+val[x];
	return;
}
int nnd(int v){
	pri[++tot]=rand();val[tot]=sum[tot]=v;siz[tot]=1;return tot;
	
}
void split(int x,int k,int &L,int &R){
	if(!x){
		L=R=0;return;
	}
	if(val[x]<=k){
		L=x;split(rs(x),k,rs(x),R);
	}
	else{
		R=x;split(ls(x),k,L,ls(x));
	}pushup(x);
	return;
}
int merge(int x,int y){
	if(!x||!y)return x|y;
	if(pri[x]>pri[y]){
		rs(x)=merge(rs(x),y);pushup(x);return x;
	}
	else{
		ls(y)=merge(x,ls(y));pushup(y);return y;
	}
}
int work(int x,int u){
	long long ans=0;
	while(u){
		if(x>=sum[ls(u)]&&x<sum[ls(u)]+val[u]){
			ans+=siz[rs(u)]+1;break;
		}
		else{
			if(x<sum[ls(u)]){
				ans+=siz[rs(u)]+1;
				u=ls(u);
			}
			else{
				x-=sum[sum[ls(u)]]+val[u];
				u=rs(u);
			}
		}
	}
	return ans;
}
long long A[maxn],fus;
int main(){
	int n=qread(),q=qread(),i,x,v,L=0,R=0,RT=0,g=0,maxs,mins;
	for(i=1;i<=n;i++)A[i]=qread();
	for(i=1;i<=n;i++){
		if(A[i]<0)fus+=A[i];
		if(A[i]>0){
			split(RT,A[i],L,R);
			L=merge(L,nnd(A[i]));RT=merge(L,R);
		}
    }
	for(i=1;i<=q;i++){
		x=qread();v=qread();
		if(A[x]<0){
			fus-=A[x];
		}
		else{
			if(A[x]>0){
                split(RT,A[x],L,R);split(L,A[x]-1,L,g);
		    	g=merge(ls(g),rs(g));L=merge(L,g);RT=merge(L,R);
			}
		}
		
		A[x]=v;
		
		if(A[x]<0){
			fus+=A[x];
		}
		if(A[x]>0){
			split(RT,A[x],L,R);
			L=merge(L,nnd(A[x]));RT=merge(L,R);			
		}
		maxs=siz[RT];
		mins=work((-fus),RT);
		cout<<maxs-mins+1<<'\n';
	}
	return 0;
}
/*
3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11872kb

input:

3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1

output:

1
2
2
2
3

result:

ok 5 number(s): "1 2 2 2 3"

Test #2:

score: 0
Accepted
time: 2ms
memory: 11880kb

input:

3 5
1 2 3
3 4
2 -2
1 3
3 1
2 1

output:

1
2
1
2
1

result:

ok 5 number(s): "1 2 1 2 1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 11728kb

input:

1 1
1000000000
1 1000000000

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

1 1
-1000000000
1 -1000000000

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 11888kb

input:

1000 1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1000
125
521
685
1000
685
1000
685
521
1000
1000
685
685
685
168
685
1000
125
685
1000
685
368
685
521
685
1000
685
368
168
685
685
685
521
1000
1000
685
685
1000
521
1
521
1000
1000
685
1000
685
125
1000
1000
521
685
1000
1000
1000
685
685
685
685
1000
168
1000
1000
685
685
685
521
1000
685
521
521...

result:

wrong answer 1st numbers differ - expected: '946', found: '1000'