QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#796279#7787. Maximum RatingUESTC_DebugSimulator#WA 1ms5704kbC++171.3kb2024-12-01 15:59:112024-12-01 15:59:11

Judging History

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

  • [2024-12-01 15:59:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5704kb
  • [2024-12-01 15:59:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200005,INF=1e9;
int n,q,a[N],cnt;
struct node{
	int ls,rs,num;
	ll sum;
}tr[N*50];
void upd(int i,int l,int r,int x,int w){
	if(l==r){
		tr[i].num+=w;
		tr[i].sum+=1ll*w*x;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid){
		if(!tr[i].ls)tr[i].ls=++cnt;
		upd(tr[i].ls,l,mid,x,w);
	}
	else{
		if(!tr[i].rs)tr[i].rs=++cnt;
		upd(tr[i].rs,mid+1,r,x,w);
	}
	tr[i].sum=tr[tr[i].ls].sum+tr[tr[i].rs].sum;
	tr[i].num=tr[tr[i].ls].num+tr[tr[i].rs].num;
}
int qry(int i,int l,int r,ll sum){
	if(l==r)return tr[i].sum<=sum;
	int mid=l+r>>1;
	if(!tr[i].ls)return qry(tr[i].rs,mid+1,r,sum);
	if(!tr[i].rs)return qry(tr[i].ls,l,mid,sum);
	if(tr[tr[i].ls].sum<sum)return tr[tr[i].ls].num+qry(tr[i].rs,mid+1,r,sum-tr[tr[i].ls].sum);
	return qry(tr[i].ls,l,mid,sum);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q;
	ll neg=0;
	int sn=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]<=0){
			sn++;
			neg-=a[i];
		}
		else upd(0,1,INF,a[i],1);
	}
	while(q--){
		int x,v;
		cin>>x>>v;
		if(a[x]>0)upd(0,1,INF,a[x],-1);
		else{
			sn--;
			neg+=a[x];
		}
		a[x]=v;
		if(a[x]>0)upd(0,1,INF,a[x],1);
		else{
			sn++;
			neg-=a[x];
		}
		int mx=n-sn;
		int mn=max(0,mx-qry(0,1,INF,neg));
		cout<<mx-mn+1<<"\n";
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3632kb

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: 1ms
memory: 5704kb

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: 0ms
memory: 3648kb

input:

1 1
1000000000
1 1000000000

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

1 1
-1000000000
1 -1000000000

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 5696kb

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:

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
1
1
1
1
1
...

result:

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