QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488112 | #6156. 冰火战士 | pavement | 0 | 3633ms | 242908kb | C++17 | 2.9kb | 2024-07-23 16:51:31 | 2024-07-23 16:51:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mt make_tuple
using ll = long long;
using ii = pair<int, int>;
using ll2 = pair<ll, ll>;
using iii = tuple<int, int, int>;
int Q, t1, s[2000005], t[2000005], x[2000005], y[2000005], k[2000005], idx[2000005];
iii c[2000005];
struct node {
node *left, *right;
int S, E;
ll sum0, sum1;
node(int _s, int _e) : S(_s), E(_e), sum0(0), sum1(0) {
if (S == E) {
return;
}
int M = (S + E) / 2;
left = new node(S, M);
right = new node(M + 1, E);
}
void upd(int p, int t, int x) {
if (S == E) {
if (t == 0) {
sum0 += x;
} else {
sum1 += x;
}
return;
}
int M = (S + E) / 2;
if (p <= M) {
left->upd(p, t, x);
} else {
right->upd(p, t, x);
}
sum0 = left->sum0 + right->sum0;
sum1 = left->sum1 + right->sum1;
}
void del(int p) {
if (S == E) {
sum0 = sum1 = 0;
return;
}
int M = (S + E) / 2;
if (p <= M) {
left->del(p);
} else {
right->del(p);
}
sum0 = left->sum0 + right->sum0;
sum1 = left->sum1 + right->sum1;
}
int get(ll pf = 0, ll sf = 0) {
if (S == E) {
if (pf + sum0 < sf + sum1) {
return S;
}
return -1;
}
if (pf + left->sum0 < sf + right->sum1) {
return max(left->E, right->get(pf + left->sum0, sf));
} else {
return left->get(pf, sf + right->sum1);
}
}
ll2 qry(int l, int r) {
if (l > E || r < S) {
return mp(0, 0);
}
if (l <= S && E <= r) {
return mp(sum0, sum1);
}
auto lq = left->qry(l, r), rq = right->qry(l, r);
return mp(lq.first + rq.first, lq.second + rq.second);
}
} *root;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> Q;
for (int i = 1; i <= Q; i++) {
cin >> s[i];
if (s[i] == 1) {
cin >> t[i] >> x[i] >> y[i];
c[++t1] = mt(x[i], t[i], i);
} else {
cin >> k[i];
}
}
sort(c + 1, c + 1 + t1);
root = new node(1, t1);
for (int i = 1; i <= Q; i++) {
if (s[i] == 1) {
idx[i] = lower_bound(c + 1, c + 1 + t1, mt(x[i], t[i], i)) - c;
root->upd(idx[i], t[i], y[i]);
//~ cout << "+ " << idx[i] << '\n';
} else {
root->del(idx[k[i]]);
}
pair<ll, int> val;
int tmp = root->get();
//~ cout << "TMP " << tmp << '\n';
for (int temp_d : {tmp - 1, tmp, tmp + 1}) {
if (!(1 <= temp_d && temp_d <= t1)) {
continue;
}
int temp = get<0>(c[temp_d]);
auto sums = root->qry(1, temp_d);
//~ cout << "! " << root->sum0 << ' ' << root->sum1 << '\n';
//~ cout << "@ " << temp << ' ' << temp_d << ' ' << sums.first << ' ' << sums.second << '\n';
ll sum0 = sums.first;
ll sum1 = root->sum1 - sums.second;
ll cur = min(sum0, sum1);
val = max(val, mp(cur, temp));
}
if (val.first == 0) {
cout << "Peace\n";
} else {
cout << val.second << ' ' << val.first * 2 << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 15928kb
input:
100 1 0 218 8134 2 1 1 0 322 4393 1 1 582 4233 1 0 426 4960 1 0 563 3003 1 1 71 7234 1 1 979 934 1 1 691 7228 1 1 723 1288 1 0 243 717 1 1 440 1860 1 1 128 76 1 0 230 4481 1 0 608 5824 2 3 1 0 107 6946 1 1 948 1161 1 1 108 5000 1 0 155 5615 2 15 1 1 927 6672 1 0 812 3669 1 1 95 7297 1 1 28 1482 2 6 ...
output:
Peace Peace Peace 322 8466 322 8466 322 8466 322 8466 426 10334 563 24712 563 24712 563 26146 563 26146 563 26146 429 29102 429 29102 563 26322 426 31086 426 33408 426 33408 230 33408 230 33408 429 45438 429 45438 429 45438 429 45438 429 45438 429 45438 344 46752 344 46752 344 46752 344 46752 344 46...
result:
wrong answer 4th lines differ - expected: '582 8466', found: '322 8466'
Test #2:
score: 0
Wrong Answer
time: 4ms
memory: 14848kb
input:
10000 1 1 617 3010 1 1 618 1611 1 1 618 8241 1 1 619 2442 1 1 620 7838 1 0 620 213 1 0 620 9615 1 1 620 5337 1 0 621 1309 1 0 622 1864 1 1 622 5158 1 1 622 348 1 0 622 3882 1 1 622 824 1 0 622 5246 1 1 622 761 1 1 623 2455 1 1 624 4419 1 1 624 8757 1 1 624 2328 1 1 625 9786 1 1 626 6994 1 1 626 2378...
output:
Peace Peace Peace Peace Peace 620 426 620 15676 620 19656 620 19656 620 19656 620 19656 620 19656 620 19656 620 19656 620 19656 620 19656 620 19656 622 27930 622 44258 622 44258 623 44258 624 44258 624 44258 624 44258 624 44258 626 45794 626 45794 626 45794 626 45794 627 45794 627 45794 627 45794 62...
result:
wrong answer 21st lines differ - expected: '624 44258', found: '623 44258'
Test #3:
score: 0
Wrong Answer
time: 3ms
memory: 15060kb
input:
10000 1 1 867 9673 1 0 868 374 1 0 868 8754 1 0 868 5112 1 1 868 866 1 0 869 5341 1 0 870 6811 1 1 870 3136 1 1 870 1543 1 1 871 6525 1 1 871 1674 1 1 872 1838 1 1 873 7148 1 1 873 3262 1 1 873 1301 1 0 873 7434 1 1 874 5359 1 0 874 2808 1 0 874 2510 1 0 874 2152 1 1 875 5263 1 1 876 7616 1 0 876 85...
output:
Peace Peace Peace Peace 868 1732 868 1732 868 1732 868 8004 868 11090 868 24140 868 27488 869 29432 870 43728 870 50252 870 52784 870 52784 870 52784 870 52784 870 52784 870 52784 870 52784 873 59898 873 59898 873 64396 873 67652 873 67652 873 67652 874 82592 874 82592 876 99688 876 99688 876 99688 ...
result:
wrong answer 12th lines differ - expected: '870 29432', found: '869 29432'
Test #4:
score: 0
Wrong Answer
time: 251ms
memory: 40740kb
input:
200000 1 0 68501 4107 1 0 114713 4264 1 0 79273 9390 1 0 59365 5025 1 1 154543 9706 1 1 195251 2745 1 1 105643 632 1 0 23703 8863 1 0 95321 2975 1 1 197593 2537 1 0 198906 3676 1 1 187265 2227 1 1 94557 9531 1 1 30342 3049 1 0 138225 2469 1 1 196601 8832 1 0 120056 743 1 0 10889 4446 1 0 3473 455 1 ...
output:
Peace Peace Peace Peace 79273 19412 79273 24902 79273 26166 59365 26166 59365 26166 68501 31240 68501 31240 68501 35694 79273 54756 79273 54756 79273 54756 94553 54770 94553 54770 94553 63662 94553 64572 79273 72420 68501 72420 79273 89468 68501 89468 79273 102226 79273 102226 79273 102226 79273 102...
result:
wrong answer 5th lines differ - expected: '154543 19412', found: '79273 19412'
Test #5:
score: 0
Wrong Answer
time: 248ms
memory: 39992kb
input:
200000 1 0 183981 1897 1 0 75105 2383 2 1 1 1 122913 2305 2 4 1 0 166063 5502 1 0 104001 4089 1 1 14 6405 1 0 115017 891 1 0 45734 9976 2 7 1 0 82385 570 1 1 33811 2907 1 0 118337 3336 1 0 80880 3103 1 0 49711 9838 1 0 70429 4710 1 1 95279 1936 1 0 135871 1761 1 0 187701 580 1 1 77073 5299 1 1 14062...
output:
Peace Peace Peace 75105 4610 Peace Peace Peace Peace Peace Peace Peace Peace Peace Peace Peace Peace Peace 45734 3872 45734 3872 45734 3872 45734 14470 45734 17256 45734 17256 45734 17256 45734 17256 45734 17256 45734 17256 45734 17256 45734 17256 54045 19952 54045 19952 54045 19952 58914 19952 4573...
result:
wrong answer 4th lines differ - expected: '122913 4610', found: '75105 4610'
Test #6:
score: 0
Wrong Answer
time: 249ms
memory: 42148kb
input:
200000 1 0 100908 5091 1 1 50240 5983 1 0 198465 1950 1 1 147925 610 1 1 107569 9345 1 0 126728 6141 1 1 157465 2742 1 0 14879 3002 2 1 1 0 174194 5987 1 0 156741 2887 1 1 159685 3784 1 0 172136 4317 1 0 170361 871 1 1 117603 1002 1 0 142251 1949 1 1 187581 9460 1 1 100500 523 1 0 167172 7820 1 0 71...
output:
Peace Peace Peace 100908 1220 107569 10182 107569 10182 107569 10182 107569 16186 126728 6704 126728 6704 126728 6704 126728 14272 126728 14272 126728 14272 126728 14272 126728 14272 157465 27958 157465 27958 157465 27958 157465 29166 156741 31972 156741 31972 157465 34430 157465 34430 157465 34430 ...
result:
wrong answer 4th lines differ - expected: '147925 1220', found: '100908 1220'
Test #7:
score: 0
Wrong Answer
time: 3633ms
memory: 242764kb
input:
2000000 1 0 1217091 107 1 0 1765937 30 2 1 2 2 1 0 758967 946 1 1 1726929 789 1 0 1866918 861 1 0 841825 869 1 0 1734601 47 1 1 877281 397 1 0 1619742 549 2 5 1 1 590165 542 1 0 332203 963 2 8 1 1 1526271 702 1 0 914523 449 1 0 1711581 229 1 1 1939244 63 1 1 645419 616 1 1 1526125 930 1 0 639503 193...
output:
Peace Peace Peace Peace Peace 758967 1578 758967 1578 758967 1578 758967 1578 841825 2372 841825 2372 877281 1738 877281 1738 841825 2372 877281 1926 1526269 1926 1526269 2824 1526269 2824 1526269 2824 1526269 2824 1526269 2824 1526125 3210 914523 4968 1190421 5100 1190421 5100 1190421 5100 1190421 ...
result:
wrong answer 6th lines differ - expected: '1726929 1578', found: '758967 1578'
Test #8:
score: 0
Wrong Answer
time: 3580ms
memory: 242652kb
input:
2000000 1 0 1846771 368 1 1 1884221 616 1 0 1582901 883 1 1 890448 498 1 0 1169093 113 1 1 858334 764 1 0 317696 641 1 0 1152391 874 1 1 1548506 552 1 0 1716021 263 1 1 1206791 754 1 1 101157 555 1 1 1229682 332 1 1 5411 776 1 0 560553 469 1 0 503881 718 1 1 1454571 850 2 4 1 1 1255962 189 1 1 46296...
output:
Peace 1884221 736 1582901 1232 1582901 1232 1582901 1232 1582901 1232 890447 1282 890447 1282 1152391 2336 1152391 2336 1206788 3256 1206788 3256 1206788 3256 1206788 3256 1206788 4194 1152391 4508 1206788 5630 1206788 5630 1206788 5630 1206788 5630 1206788 5630 1206788 6202 1152391 6586 1152391 658...
result:
wrong answer 3rd lines differ - expected: '1884221 1232', found: '1582901 1232'
Test #9:
score: 0
Wrong Answer
time: 3582ms
memory: 242908kb
input:
2000000 1 0 933589 540 1 0 1332805 804 1 1 726913 60 1 0 582566 540 1 0 1541647 266 1 0 61185 227 1 0 44006 722 2 1 1 1 1100826 318 1 1 1583347 709 1 1 488319 941 2 10 1 0 1929473 528 2 13 1 1 1077416 855 1 0 1182411 885 1 0 1667425 768 1 1 1383821 403 1 0 187972 894 1 1 1583116 592 1 1 242066 187 2...
output:
Peace Peace Peace 582566 120 582566 120 61185 120 44006 120 44006 120 44006 756 582566 2174 582566 2174 488317 1898 488317 1898 488317 1898 582566 2466 582566 2466 582566 2466 1077416 2978 488317 3686 582566 4456 582566 4456 582566 4456 1077416 4766 1077416 4766 1077416 4766 651473 5090 726913 6300 ...
result:
wrong answer 4th lines differ - expected: '726913 120', found: '582566 120'
Test #10:
score: 0
Wrong Answer
time: 3547ms
memory: 242624kb
input:
2000000 1 0 267659481 924 1 1 211034569 948 1 1 760144421 564 1 1 657639999 860 1 0 180151690 350 2 4 1 1 99406176 793 2 3 1 1 81357121 972 1 0 260132781 642 1 0 7161061 191 1 1 245955169 633 1 1 387566565 485 1 1 72982881 592 1 1 141574651 711 1 1 88299089 143 1 0 355273696 723 1 1 19210825 454 1 0...
output:
Peace Peace 267659481 1128 657639207 1848 657639207 2548 267659481 1128 267659481 1128 211034513 700 211034513 700 211034513 700 211034513 1082 245954398 1082 245954398 1082 245954398 1082 245954398 1082 245954398 1082 245954398 1082 245954398 1082 211034513 3016 211034513 3942 211034513 3942 211034...
result:
wrong answer 3rd lines differ - expected: '760144421 1128', found: '267659481 1128'