QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#790733 | #7787. Maximum Rating | zhilin# | WA | 2ms | 11888kb | C++14 | 2.0kb | 2024-11-28 15:03:34 | 2024-11-28 15:03:34 |
Judging History
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'