QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#796279 | #7787. Maximum Rating | UESTC_DebugSimulator# | WA | 1ms | 5704kb | C++17 | 1.3kb | 2024-12-01 15:59:11 | 2024-12-01 15:59:11 |
Judging History
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'