QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671020#6156. 冰火战士propane100 ✓1998ms84612kbC++203.4kb2024-10-24 09:58:362024-10-24 09:58:36

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 09:58:36]
  • 评测
  • 测评结果:100
  • 用时:1998ms
  • 内存:84612kb
  • [2024-10-24 09:58:36]
  • 提交

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