QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#671020 | #6156. 冰火战士 | propane | 100 ✓ | 1998ms | 84612kb | C++20 | 3.4kb | 2024-10-24 09:58:36 | 2024-10-24 09:58:36 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 2e6 + 5;
// LL tr[maxn * 4];
// void modify(int u, int l, int r, int x, int v){
// if (l == r){
// tr[u] += v;
// return;
// }
// int mid = (l + r) / 2;
// if (x <= mid) modify(2 * u, l, mid, x, v);
// else modify(2 * u + 1, mid + 1, r, x, v);
// tr[u] = tr[2 * u] + tr[2 * u + 1];
// }
// int find_first(int u, int l, int r, LL target){
// if (tr[u] < target) return r + 1;
// if (l == r) return r;
// int mid = (l + r) / 2;
// if (tr[2 * u] >= target) return find_first(2 * u, l, mid, target);
// return find_first(2 * u + 1, mid + 1, r, target - tr[2 * u]);
// }
struct BIT{
LL tr[maxn];
int lowbit(int x){
return x & -x;
}
void modify(int x, LL v){
while(x < maxn){
tr[x] += v;
x += lowbit(x);
}
}
LL query(int x){
LL ans = 0;
while(x){
ans += tr[x];
x -= lowbit(x);
}
return ans;
}
LL query(int l, int r){
return query(r) - query(l - 1);
}
int find_first(LL sum){
int ans = 0; LL val = 0;
for(int i = 21; i >= 0; i--){
if ((ans | (1 << i)) < maxn && val + tr[ans | (1 << i)] < sum){
ans |= 1 << i;
val += tr[ans];
}
}
return ans + 1;
}
}bit[3];
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
vector<int> nums;
vector<array<int, 4> > ops(n);
for(int i = 0; i < n; i++){
int op;
cin >> op;
if (op == 1){
int t, x, y;
cin >> t >> x >> y;
ops[i] = {1, t, x, y};
nums.push_back(x);
}
else{
int x;
cin >> x;
x--;
ops[i] = {2, x};
}
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
auto get = [&](int x){
return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1;
};
const int m = nums.size();
for(auto &[op, t, x, y] : ops){
if (op == 1){
x = get(x);
bit[t].modify(x, y);
bit[2].modify(x, y);
}
else{
auto [_, tt, xx, yy] = ops[t];
bit[tt].modify(xx, -yy);
bit[2].modify(xx, -yy);
}
int pos = bit[2].find_first(bit[1].query(m));
LL mx = 0;
for(int i = -2; i <= 2; i++){
int t = pos + i;
if (t >= 1 and t <= m){
LL cost = min(bit[0].query(t), bit[1].query(m) - bit[1].query(t - 1));
mx = max(mx, cost);
}
}
if (mx == 0) cout << "Peace" << '\n';
else{
LL remain = bit[1].query(m) - mx + 1;
int pos = bit[1].find_first(remain);
if (bit[1].query(pos, m) < mx) pos--;
if (bit[1].query(pos + 1, m) >= mx) pos++;
cout << nums[pos - 1] << ' ' << 2 * mx << '\n';
}
}
}
詳細信息
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 24088kb
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 582 8466 582 8466 582 8466 582 8466 582 10334 582 24712 582 24712 582 26146 582 26146 582 26146 440 29102 440 29102 582 26322 440 31086 440 33408 440 33408 440 33408 440 33408 440 45438 440 45438 440 45438 440 45438 440 45438 440 45438 440 46752 440 46752 440 46752 440 46752 440 46...
result:
ok 100 lines
Test #2:
score: 10
Accepted
time: 7ms
memory: 26228kb
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 624 44258 624 44258 624 44258 624 44258 625 44258 626 45794 626 45794 626 45794 626 45794 628 45794 628 45794 628 45794 62...
result:
ok 10000 lines
Test #3:
score: 10
Accepted
time: 5ms
memory: 26232kb
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 870 29432 870 43728 870 50252 870 52784 870 52784 871 52784 871 52784 871 52784 871 52784 871 52784 873 59898 873 59898 873 64396 873 67652 873 67652 873 67652 874 82592 875 82592 876 99688 876 99688 876 99688 ...
result:
ok 10000 lines
Test #4:
score: 10
Accepted
time: 138ms
memory: 29140kb
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 154543 19412 154543 24902 105643 26166 105643 26166 105643 26166 105643 31240 105643 31240 105643 35694 94557 54756 94557 54756 94557 54756 94557 54770 94557 54770 94557 63662 94557 64572 94557 72420 94557 72420 94557 89468 94557 89468 81597 102226 81597 102226 81597 102226 8...
result:
ok 200000 lines
Test #5:
score: 10
Accepted
time: 139ms
memory: 29004kb
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 122913 4610 Peace Peace Peace Peace Peace Peace Peace Peace Peace Peace Peace Peace Peace 95279 3872 95279 3872 95279 3872 77073 14470 77073 17256 77073 17256 77073 17256 77073 17256 77073 17256 77073 17256 77073 17256 77073 17256 54047 19952 54047 19952 54047 19952 58917 19952 540...
result:
ok 200000 lines
Test #6:
score: 10
Accepted
time: 145ms
memory: 27424kb
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 147925 1220 107569 10182 107569 10182 107569 10182 107569 16186 147925 6704 147925 6704 147925 6704 147925 14272 147925 14272 147925 14272 147925 14272 147925 14272 157465 27958 157465 27958 157465 27958 157465 29166 157465 31972 157465 31972 157465 34430 157465 34430 157465 34430 ...
result:
ok 200000 lines
Test #7:
score: 10
Accepted
time: 1834ms
memory: 70200kb
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 1726929 1578 1726929 1578 1726929 1578 1726929 1578 877281 2372 877281 2372 877281 1738 877281 1738 877281 2372 877281 1926 1526271 1926 1526271 2824 1526271 2824 1526271 2824 1526271 2824 1526271 2824 1526125 3210 1526125 4968 1190423 5100 1190423 5100 1190423 5100 119...
result:
ok 2000000 lines
Test #8:
score: 10
Accepted
time: 1869ms
memory: 68272kb
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 1884221 1232 1884221 1232 1884221 1232 1884221 1232 890448 1282 890448 1282 1548506 2336 1548506 2336 1206791 3256 1206791 3256 1206791 3256 1206791 3256 1206791 4194 1206791 4508 1206791 5630 1206791 5630 1206791 5630 1206791 5630 1206791 5630 1206791 6202 1206791 6586 1206791 658...
result:
ok 2000000 lines
Test #9:
score: 10
Accepted
time: 1897ms
memory: 70140kb
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 726913 120 726913 120 726913 120 726913 120 726913 120 726913 756 726913 2174 726913 2174 488319 1898 488319 1898 488319 1898 726913 2466 726913 2466 726913 2466 1077416 2978 488319 3686 726913 4456 726913 4456 726913 4456 1077416 4766 1077416 4766 1077416 4766 726913 5090 726913 6...
result:
ok 2000000 lines
Test #10:
score: 10
Accepted
time: 1998ms
memory: 84612kb
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 760144421 1128 657639999 1848 657639999 2548 760144421 1128 760144421 1128 211034569 700 211034569 700 211034569 700 211034569 1082 245955169 1082 245955169 1082 245955169 1082 245955169 1082 245955169 1082 245955169 1082 245955169 1082 211034569 3016 211034569 3942 211034569 3942 211034...
result:
ok 2000000 lines
Extra Test:
score: 0
Extra Test Passed