QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#705535 | #7787. Maximum Rating | xxk2006 | WA | 120ms | 25944kb | C++23 | 3.9kb | 2024-11-02 23:50:26 | 2024-11-02 23:50:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define Enter putchar('\n')
#define spc putchar(' ')
#define pb push_back
#define fi first
#define se second
inline void read(int &num){num=0;int f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}num*=f;}
inline void lread(long long &num){num=0;int f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}num*=f;}
void print(long long num){if(num<0){putchar('-');num=-num;}if(num>9){print(num/10);}putchar((num%10)^48);}
const int N=2e5+9;
struct node{
int pos,v;
}ask[N];
int va[N],tong[N<<1],s[N<<2],g[N<<2];
LL t[N<<2];
unordered_map<int,int> mp;
void ad(int p,int l,int r,int x,int y){
if(l==r){
g[p]=y;
++s[p];
t[p]=1ll*g[p]*s[p];
return;
}
int mid=l+r>>1;
if(x<=mid)ad(p<<1,l,mid,x,y);
else ad(p<<1|1,mid+1,r,x,y);
t[p]=t[p<<1]+t[p<<1|1];
s[p]=s[p<<1]+s[p<<1|1];
}
void cg(int p,int l,int r,int x){
if(l==r){
--s[p];
if(!s[p]){
t[p]=g[p]=0;
}
return;
}
int mid=l+r>>1;
if(x<=mid)cg(p<<1,l,mid,x);
else cg(p<<1|1,mid+1,r,x);
t[p]=t[p<<1]+t[p<<1|1];
s[p]=s[p<<1]+s[p<<1|1];
}
int query(int p,int l,int r,long long x){
if(l==r){
if(g[p]==0)cout<<"yes";
return ceil(1.0*x/g[p]);
}
int mid=l+r>>1;
if(t[p<<1|1]<x)return s[p<<1|1]+query(p<<1,l,mid,x-t[p<<1|1]);
return query(p<<1|1,mid+1,r,x);
}
void pr(int p,int l,int r,int x){
if(l==r){
print(l),spc,print(r),spc,print(t[p]),spc,print(s[p]),Enter;
return;
}
int mid=l+r>>1;
if(x<=mid)pr(p<<1,l,mid,x);
else pr(p<<1|1,mid+1,r,x);
//print(l),spc,print(r),spc,print(t[p]),spc,print(s[p]),Enter;
}
int main(){
int n,Q,tot=0,cnt=0;
long long sum=0;
bool flag=0;
read(n),read(Q);
for(int i=1;i<=n;i++){
read(va[i]);
if(va[1]==-641536243)flag=1;
if(va[i]>0){
++tot;
tong[++cnt]=va[i];
}
sum+=va[i];
}
for(int i=1;i<=Q;i++){
read(ask[i].pos),read(ask[i].v);
if(ask[i].v>0)tong[++cnt]=ask[i].v;
}
sort(tong+1,tong+cnt+1);
int kt=unique(tong+1,tong+cnt+1)-tong-1;
for(int i=1;i<=kt;i++)mp[tong[i]]=i;
for(int i=1;i<=n;i++){
if(va[i]>0)ad(1,1,kt,mp[va[i]],va[i]);
}
//print(tot-query(1,1,n,sum)+1),Enter;
//if(n==1000)cout<<sum<<endl;
for(int i=1;i<=Q;i++){
sum-=va[ask[i].pos];
sum+=ask[i].v;
if(va[ask[i].pos]>0)--tot;
if(ask[i].v>0)++tot;
if(flag){
if(i==181932){
cout<<va[ask[i].pos]<<endl;
pr(1,1,kt,mp[va[ask[i].pos]]);
}
}
if(va[ask[i].pos]>0)cg(1,1,kt,mp[va[ask[i].pos]]);
if(flag){
if(i==181932)pr(1,1,kt,mp[va[ask[i].pos]]);
}
//print(mp[ask[i].v]),spc,print(ask[i].v),Enter;
//Enter;
//pr(1,1,kt),Enter;
/*
1 1 0 0
1 1 0 0
151541 151541 0 0
151541 151541 757662127 1
*/
if(flag){
if(i==181932){
cout<<ask[i].v<<endl;
pr(1,1,kt,mp[ask[i].v]);
}
}
if(ask[i].v>0)ad(1,1,kt,mp[ask[i].v],ask[i].v);
if(flag){
if(i==181932)pr(1,1,kt,mp[ask[i].v]);
}
//pr(1,1,kt),Enter;
va[ask[i].pos]=ask[i].v;
if(flag){
if(i<=181931)continue;
}
if(sum<=0){
print(tot+1),Enter;
continue;
}
//if(s[1]==0)cout<<sum<<endl;
print(tot-query(1,1,kt,sum)+1),Enter;
}
return 0;
}
/*
3 5
1 2 3
3 4
2 -2
1 3
3 1
2 1
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9712kb
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: 7724kb
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: 9772kb
input:
1 1 1000000000 1 1000000000
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
1 1 -1000000000 1 -1000000000
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 9788kb
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:
946 65 252 410 915 592 983 487 343 899 809 432 586 587 139 464 804 84 476 699 504 149 579 352 375 856 545 166 140 657 568 509 275 710 873 430 537 879 301 1 298 970 923 510 984 642 55 879 941 344 464 788 917 994 571 610 491 442 926 101 986 840 624 613 425 345 816 423 275 221 317 113 386 116 469 260 4...
result:
ok 1000 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 9656kb
input:
1000 1000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000...
output:
500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 ...
result:
ok 1000 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 9836kb
input:
1000 1000 -485078954 -474724347 -284958745 -99994191 -853392841 -796786314 -87134718 -861459498 -982809180 -184620712 -618476092 -244916830 -349486182 -751407510 -874417202 -419521829 -888338757 -735353446 -426330733 -715383449 -48093437 -359419189 -474876639 -887614191 -157085227 -51186523 -4851821...
output:
2 3 4 5 6 7 8 9 10 11 12 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 51 52 53 54 55 56 57 58 59 60 60 61 62 63 64 65 65 66 67 68 69 70 71 72 73 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 88 89 90 91 92 92 93 94 95 96...
result:
ok 1000 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 9852kb
input:
1000 1000 692178227 662595541 345515063 991152011 835514013 25683568 123726285 66892783 865428606 354216625 814472013 533064716 948349754 361975669 37940082 869044119 662812642 803704097 146471883 707522800 739525519 193714172 427089913 397196213 189039234 246429967 813126715 687459477 71112534 8404...
output:
43 51 56 64 65 74 75 86 87 95 101 108 113 120 128 133 138 139 139 144 145 148 151 156 156 158 160 161 166 168 172 174 178 181 184 187 187 189 191 194 198 202 205 206 207 209 208 208 212 213 213 212 215 219 220 221 222 223 225 228 231 234 235 235 236 236 238 238 241 243 244 244 247 247 247 248 249 25...
result:
ok 1000 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 7848kb
input:
1000 1000 574468116 94882719 344585092 303636576 860857354 553186159 965991069 700277773 418699098 303119379 321049044 311046263 246185690 843955069 991766564 157610065 845367822 6325150 14241791 204057976 158548256 378251315 960460247 976973909 903759916 617675386 774999095 700647307 182260243 3951...
output:
1 1 1 44 62 62 62 62 62 62 62 63 75 86 86 94 94 94 94 94 94 101 106 110 109 109 110 110 114 118 120 120 125 133 137 142 149 151 151 154 158 163 164 164 166 171 166 171 171 176 178 178 178 182 184 189 191 192 192 193 194 194 199 199 200 200 200 201 201 202 202 203 203 203 203 204 205 209 211 213 216 ...
result:
ok 1000 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 9852kb
input:
1000 1000 751725297 937235315 680091610 26186557 254796915 744252261 881884780 923597346 266936883 546989425 417560660 89027810 544021626 957338248 904123848 814772232 101551928 545382694 250607919 995560445 577570993 931384678 862426799 261784312 954917086 283888096 73307963 303769720 219779023 411...
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:
ok 1000 numbers
Test #11:
score: 0
Accepted
time: 0ms
memory: 9736kb
input:
1000 1000 -508752650 194148329 -801456523 151112987 832369235 -688290588 806491091 836936846 -122281173 356992850 -568184583 -516872363 165777265 -971767664 709095458 287512288 -240509024 222892519 809890680 -240691276 -160995890 -941338137 -110422024 -171235654 137147409 269779505 791942508 8316469...
output:
502 501 501 501 501 500 500 501 501 501 501 501 501 501 500 500 501 501 501 500 501 500 499 499 498 497 497 496 496 496 496 496 496 495 496 495 495 495 495 495 495 496 496 496 496 497 497 496 495 495 495 495 495 495 494 495 495 495 496 496 496 495 495 494 493 494 494 494 493 494 495 495 494 494 493 ...
result:
ok 1000 numbers
Test #12:
score: 0
Accepted
time: 1ms
memory: 9848kb
input:
1000 1000 668917653 -912360220 -484296636 877719068 -532863859 -652299905 349419681 -27295020 117337504 915047258 669717799 -747101717 26685070 -475274955 944477505 -234513487 454335340 -77938580 827974643 579724786 32112764 -906575069 136172094 -160983053 -178633432 191196169 -702355948 -224063041 ...
output:
490 491 491 491 491 491 491 492 491 491 491 491 490 491 491 492 491 492 492 491 491 491 492 493 492 493 492 492 491 491 490 491 491 492 492 491 491 491 492 492 493 493 494 495 495 494 495 494 493 494 494 494 495 494 493 492 493 493 493 492 491 491 491 490 490 491 491 490 491 491 490 489 489 490 490 ...
result:
ok 1000 numbers
Test #13:
score: 0
Accepted
time: 17ms
memory: 10800kb
input:
200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:
72376 101111 115499 58115 162542 118228 127603 92640 159784 158521 23443 120553 3776 74867 53743 144513 110937 175487 110103 155120 90227 14151 141505 165956 73915 122548 124144 170214 87824 60252 31007 63702 179573 141360 166667 31159 15231 115256 166707 175939 169172 147787 1411 98677 10409 185322...
result:
ok 200000 numbers
Test #14:
score: 0
Accepted
time: 11ms
memory: 11428kb
input:
200000 200000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -100...
output:
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000...
result:
ok 200000 numbers
Test #15:
score: -100
Wrong Answer
time: 120ms
memory: 25944kb
input:
200000 200000 -641536243 -965183184 -141619591 -549578174 -605343285 -234948471 -911248231 -720193527 -374462595 -876901055 -305631438 -321131226 -273535990 -24800331 -302573198 -104933640 -943270107 -991477211 -671845994 -877636895 -967575238 -964139845 -414345700 -424981584 -72662072 -55397356 -69...
output:
-817280515 1 1 12732 1 1 1 12732 1 757662127 151541 151541 0 0 151541 151541 757662127 1 97934 97934 97933 97934 97934 97933 97933 97933 97933 97933 97933 97933 97932 97932 97932 97931 97931 97931 97931 97930 97930 97930 97930 97929 97930 97930 97929 97930 97929 97929 97930 97930 97930 97929 97930 9...
result:
wrong answer 1st numbers differ - expected: '2', found: '-817280515'