QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#635422 | #7787. Maximum Rating | yell | RE | 425ms | 170724kb | C++20 | 2.1kb | 2024-10-12 19:46:21 | 2024-10-12 19:46:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 100;
const int INF = 1e9;
int tot = 1;
struct node {
int lson, rson, num;
LL sum;
} seg[N * 45];
#define ls seg[id].lson
#define rs seg[id].rson
void pushdown(int id) {
if (!ls) {
ls = ++tot;
seg[ls].num = seg[ls].sum = 0;
}
if (!rs) {
rs = ++tot;
seg[rs].num = seg[rs].sum = 0;
}
}
void pushup(int id) {
seg[id].sum = seg[ls].sum + seg[rs].sum;
seg[id].num = seg[ls].num + seg[rs].num;
}
void modify(int id, int l, int r, int pos, int val) {
if (l == r) {
seg[id].num += val;
seg[id].sum += pos * val;
return;
}
pushdown(id);
int mid = (l + r) / 2;
if (pos <= mid) {
modify(ls, l, mid, pos, val);
} else {
modify(rs, mid + 1, r, pos, val);
}
pushup(id);
}
LL query(int id, int l, int r, LL sum) {
if (id == 0) return 0;
if (l == r) {
return (sum <= 0 ? 0 : (sum + l - 1) / l);
}
int mid = (l + r) / 2;
if (seg[rs].sum >= sum) {
return query(rs, mid + 1, r, sum);
} else {
return query(ls, l, mid, sum - seg[rs].sum) + seg[rs].num;
}
}
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
LL sum = 0;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
if (a[i] > 0) {
modify(1, 1, INF, a[i], 1);
cnt++;
}
}
while (q--) {
int idx, val;
cin >> idx >> val;
if (a[idx] > 0) {
modify(1, 1, INF, a[idx], -1);
cnt--;
}
if (val > 0) {
modify(1, 1, INF, val, 1);
cnt++;
}
sum = sum - a[idx] + val;
a[idx] = val;
cout << cnt - query(1, 1, INF, sum) + 1 << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 0ms
memory: 3560kb
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: 3564kb
input:
1 1 1000000000 1 1000000000
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
1 1 -1000000000 1 -1000000000
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3572kb
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: 1ms
memory: 3640kb
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: 4508kb
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: 2ms
memory: 6044kb
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: 0ms
memory: 7000kb
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: 2ms
memory: 6704kb
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: 6120kb
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: 4804kb
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: 103ms
memory: 4000kb
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: 50ms
memory: 3836kb
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: 0
Accepted
time: 223ms
memory: 120920kb
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:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102...
result:
ok 200000 numbers
Test #16:
score: 0
Accepted
time: 305ms
memory: 122144kb
input:
200000 200000 535720938 467103996 857450438 172971807 714967349 587521411 299612773 913191463 178807897 661936283 790880177 161883029 24299945 457179067 314816794 183632306 607881293 211143843 900956623 913865574 820043720 588993518 487620852 859828820 273462389 315848062 600304728 176203396 8209093...
output:
546 590 723 815 911 1092 1234 1331 1383 1431 1546 1570 1606 1688 1775 1865 1924 1928 2018 2102 2146 2222 2283 2310 2367 2434 2509 2527 2528 2605 2643 2681 2694 2725 2773 2798 2815 2878 2915 2970 2982 3042 3095 3135 3152 3208 3232 3281 3331 3387 3433 3484 3539 3542 3585 3629 3634 3653 3664 3703 3732 ...
result:
ok 200000 numbers
Test #17:
score: 0
Accepted
time: 425ms
memory: 170724kb
input:
200000 200000 418010827 604423883 192956954 559085301 108906910 115024001 141877556 841543744 27045682 610839037 928860990 234831867 617103173 865529539 563610567 177230961 495469180 750201387 768726531 41804530 944099165 142126879 94620113 439606515 324619559 613464554 898613597 147922029 268493569...
output:
407 407 686 686 903 903 903 903 1040 1040 1169 1276 1276 1276 1373 1373 1392 1447 1487 1487 1576 1616 1726 1825 1927 2019 2084 2084 2084 2084 2106 2106 2183 2183 2236 2236 2236 2298 2323 2356 2356 2366 2366 2380 2380 2380 2380 2396 2448 2448 2448 2448 2448 2448 2463 2463 2506 2552 2552 2552 2581 263...
result:
ok 200000 numbers
Test #18:
score: -100
Runtime Error
input:
200000 200000 595268008 741743770 192026983 576602575 134250251 306090103 352738559 769896025 875283467 854709084 730405313 12813414 619971818 52541645 181000559 834393128 751653288 952822441 341529147 833306999 363121902 31696730 627990446 93013138 375776729 279677264 491889757 456077151 674608570 ...
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 ...