QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#133194#6630. Triangle CollectionCyanmond5 945ms39044kbC++147.8kb2023-08-01 17:24:132023-08-01 17:24:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-01 17:24:16]
  • 评测
  • 测评结果:5
  • 用时:945ms
  • 内存:39044kb
  • [2023-08-01 17:24:13]
  • 提交

answer

#include <bits/stdc++.h>
// #include "atcoder/modint"

using i64 = long long;
// using Fp = atcoder::modint998244353;

int op(int a, int b) {
    return std::min(a, b);
}
int e() {
    return 0;
}
int mapping(int a, int b) {
    return a + b;
}
int composition(int a, int b) {
    return a + b;
}
int id() {
    return 0;
}

class LazySegTree {
    int n, size, log;
    std::vector<int> data, lazy;

    void upd(int i) {
        data[i] = op(data[2 * i], data[2 * i + 1]);
    }
    void app(int k, int f) {
        data[k] = mapping(f, data[k]);
        if (k < size) lazy[k] = composition(f, lazy[k]);
    }
    void push(int k) {
        app(2 * k, lazy[k]);
        app(2 * k + 1, lazy[k]);
        lazy[k] = id();
    }

    public:
    LazySegTree(int n_) : n(n_) {
        log = 1;
        while ((1 << log) < n) ++log;
        size = 1 << log;
        data.assign(2 * size, e());
        lazy.assign(size, id());
    }

    int fold(int l, int r) {
        if (l == r) return e();
        l += size;
        r += size;
        for (int d = log; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }

        int ret = 1 << 30;
        while (l < r) {
            if (l % 2 == 1) ret = op(ret, data[l++]);
            if (r % 2 == 1) ret = op(ret, data[--r]);
            l /= 2;
            r /= 2;
        }
        return ret;
    }

    int allfold() {
        return data[1];
    }

    void apply(int l, int r, int f) {
        l += size;
        r += size;
        for (int d = log; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }

        int l2 = l, r2 = r;
        while (l < r) {
            if (l % 2 == 1) app(l++, f);
            if (r % 2 == 1) app(--r, f);
            l /= 2;
            r /= 2;
        }
        l = l2;
        r = r2;

        for (int d = 1; d <= log; ++d) {
            if (((l >> d) << d) != l) upd(l >> d);
            if (((r >> d) << d) != r) upd((r - 1) >> d);
        }
    }

    int get(int i) {
        return fold(i, i + 1);
    }

    void set(int i, int v) {
        apply(i, i + 1, v - get(i));
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<i64> C(N + 1);
    for (int i = 1; i <= N; ++i) {
        std::cin >> C[i];
    }

    std::vector<i64> L(Q), D(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> L[i] >> D[i];
    }

    /*
    if (N <= 2000 and Q <= 2000) {
        for (int q = 0; q < Q; ++q) {
            C[L[q]] += D[q];

            std::vector<int> O;
            for (int i = 1; i <= N; ++i) {
                if (C[i] % 2 == 1) {
                    O.push_back(i);
                }
            }
            auto D = C;
            for (auto &e : D) e = e / 2;

            int i = N;
            std::reverse(O.begin(), O.end());
            i64 ans = 0;
            for (const auto s : O) {
                while (i != 0 and D[i] == 0) --i;
                const int l = s / 2 + 1;
                if (i >= l) {
                    --D[i];
                    ++ans;
                }
            }
            i64 sum = 0;
            for (auto e : D) sum += e;
            ans += sum * 2 / 3;
            std::cout << ans << std::endl;
        }
        return 0;
    }
    */
    // subtask 3
    std::multiset<int> a, b, x, y;
    i64 s1 = 0;
    for (int i = 1; i <= N; ++i) {
        if (C[i] % 2 == 1) a.insert(i);
    }
    for (int i = N; i >= 1; --i) {
        i64 d = C[i];
        while (x.size() <= N + Q and d - 2 >= 0) {
            d -= 2;
            x.insert(i);
        }
        s1 += d / 2;
    }
    int p = 0;

    LazySegTree seg(N + 1);
    for (int i = 0; i <= N; ++i) seg.set(i, 0);
    while (true) {
        if (a.empty() or x.empty()) break;
        const int u = *a.begin(), v = *x.rbegin();
        seg.apply((u / 2) + 1, N + 1, 1);
        seg.apply(v, N + 1, -1);
        if (seg.allfold() < 0) {
            seg.apply((u / 2) + 1, N + 1, -1);
            seg.apply(v, N + 1, 1);
            break;
        } else {
            ++p;
            a.erase(a.find(u));
            x.erase(x.find(v));
            b.insert(u);
            y.insert(v);
        }
    }

    /*
    for (const auto e : a) std::cerr << e << ' ';
    std::cerr << std::endl;
    for (const auto e : b) std::cerr << e << ' ';
    std::cerr << std::endl;
    for (const auto e : x) std::cerr << e << ' ';
    std::cerr << std::endl;
    for (const auto e : y) std::cerr << e << ' ';
    std::cerr << std::endl;
    */

    auto upd = [&]() {
        while (seg.allfold() < 0) {
            const int u = *b.rbegin(), v = *y.begin();
            seg.apply((u / 2) + 1, N + 1, -1);
            seg.apply(v, N + 1, 1);
            --p;
            b.erase(b.find(u));
            y.erase(y.find(v));
            a.insert(u);
            x.insert(v);
        }
        while (true) {
            if (a.empty() or x.empty()) break;
            const int u = *a.begin(), v = *x.rbegin();
            seg.apply((u / 2) + 1, N + 1, 1);
            seg.apply(v, N + 1, -1);
            if (seg.allfold() < 0) {
                seg.apply((u / 2) + 1, N + 1, -1);
                seg.apply(v, N + 1, 1);
                break;
            } else {
                ++p;
                a.erase(a.find(u));
                x.erase(x.find(v));
                b.insert(u);
                y.insert(v);
            }
        }
    };

    auto erase = [&](int v, bool bx) {
        if (bx) {
            if (a.find(v) != a.end()) {
                a.erase(a.find(v));
            } else if (b.find(v) != b.end()) {
                seg.apply((v / 2) + 1, N + 1, -1);
                const int o = *y.begin();
                seg.apply(o, N + 1, 1);
                y.erase(y.find(o));
                x.insert(o);
                b.erase(b.find(v));
                --p;
            }
            return;
        }
        if (x.find(v) != x.end()) {
            x.erase(x.find(v));
        } else if (y.find(v) != y.end()) {
            seg.apply(v, N + 1, 1);
            const int o = *b.rbegin();
            seg.apply((o / 2) + 1, N + 1, -1);
            b.erase(b.find(o));
            a.insert(o);
            y.erase(y.find(v));
            --p;
        }
    };


    auto rollback = [&]() {
        if (b.empty()) return;
        const int u = *b.rbegin(), v = *y.begin();
        seg.apply((u / 2) + 1, N + 1, -1);
        seg.apply(v, N + 1, 1);
        --p;
        b.erase(b.find(u));
        y.erase(y.find(v));
        a.insert(u);
        x.insert(v);
    };

    auto adda = [&](int v) {
        a.insert(v);
        rollback();
        upd();
    };

    auto addx = [&](int v) {
        x.insert(v);
        rollback();
        upd();
    };

    for (int q = 0; q < Q; ++q) {
        if (C[L[q]] % 2 == 1) {
            erase(L[q], true);
        } else {
            if (C[L[q]] >= 2 and D[q] == -1) {
                if (x.find(L[q]) == x.end() and y.find(L[q]) == y.end()) {
                    --s1;
                } else erase(L[q], false);
            }
        }
        //td::cerr << p << std::endl;
        C[L[q]] += D[q];
        if (C[L[q]] % 2 == 1) adda(L[q]);
        else if (D[q] == 1) addx(L[q]);
        upd();
        std::cout << p + (x.size() + s1) * 2 / 3 << '\n';
    }

    /*
    if (std::all_of(D.begin(), D.end(), [&](int v) {
        return std::abs(v) <= 1;
    })) {
        // subtask 4

    } else {
        // subtask 3

    }
    */
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3536kb

input:

1 23
1485
1 -12
1 -30
1 -20
1 6
1 24
1 5
1 31
1 14
1 -34
1 -22
1 -45
1 37
1 46
1 9
1 22
1 -9
1 9
1 -46
1 -47
1 39
1 36
1 -36
1 50

output:

495
495
495
495
495
494
495
495
495
495
494
495
495
494
494
495
494
494
495
494
494
494
494

result:

wrong answer 1st numbers differ - expected: '491', found: '495'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 1ms
memory: 3620kb

input:

1999 2000
1 1 1 1 0 2 0 2 1 0 2 1 2 2 2 1 2 0 0 1 2 2 0 1 0 1 0 2 0 0 2 1 1 1 1 0 1 2 1 2 1 1 1 1 1 0 2 2 0 2 1 1 2 0 0 2 0 0 2 1 2 0 0 1 1 2 0 2 2 2 1 2 0 2 1 2 0 1 2 2 2 1 1 2 1 1 1 1 0 0 1 1 0 1 2 1 0 0 2 0 2 2 2 0 1 1 2 0 0 1 0 0 2 1 2 1 2 0 1 1 2 2 0 0 1 2 2 1 2 1 2 2 2 0 0 1 1 2 1 1 2 2 2 2 2 ...

output:

660
660
660
661
661
661
661
660
660
660
660
660
661
661
662
662
661
660
661
661
660
660
661
661
661
661
661
661
661
661
661
661
661
660
660
660
660
659
659
660
660
660
661
662
662
662
662
662
662
662
662
662
662
662
662
662
662
663
662
662
662
662
662
662
662
662
663
663
662
663
663
663
662
662
661
...

result:

wrong answer 12th numbers differ - expected: '661', found: '660'

Subtask #4:

score: 5
Accepted

Test #35:

score: 5
Accepted
time: 5ms
memory: 3736kb

input:

2000 1999
0 1 0 3 0 1 0 0 0 0 0 0 0 2 0 0 0 0 3 1 1 0 2 0 0 3 0 0 0 0 0 4 0 0 1 0 1 0 0 0 0 1 2 1 0 0 0 0 7 0 1 3 1 0 1 1 0 3 2 1 0 1 1 3 3 1 0 2 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 1 2 3 0 1 0 3 3 0 0 0 0 1 0 1 2 0 0 2 2 0 1 2 1 2 0 0 0 1 1 0 1 2 0 0 0 0 2 0 5 0 0 0 0 0 1 0 0 2 0 1 2 0 1 0 0 0 2 0 ...

output:

666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
666
665
665
665
665
665
665
665
665
665
665
665
665
665
665
665
665
665
666
666
666
666
666
666
666
666
666
666
666
666
666
665
...

result:

ok 1999 numbers

Test #36:

score: 0
Accepted
time: 5ms
memory: 3868kb

input:

1999 2000
938865181 635701131 720186551 12098533 888342577 819466162 677119886 695501777 87063160 544120940 280740814 953384275 462378756 394423771 769842478 563100233 988726627 938258387 941725041 202877851 608668845 507891555 488072389 600920090 738211573 440041095 584208199 334345340 587249363 60...

output:

334310744804
334310744804
334310744805
334310744805
334310744805
334310744805
334310744805
334310744806
334310744805
334310744805
334310744805
334310744805
334310744805
334310744805
334310744805
334310744805
334310744805
334310744805
334310744805
334310744804
334310744805
334310744804
334310744805
3...

result:

ok 2000 numbers

Test #37:

score: 0
Accepted
time: 5ms
memory: 3916kb

input:

1998 2000
953983734 995770518 938631730 961951570 959332856 972648102 943061680 904445058 924304353 960622114 906426330 931936027 957313612 965894280 965137632 988149861 916855162 928712995 923621242 962852409 971372933 948162818 943268160 970351693 997138667 985041992 953192885 954772005 986919660 ...

output:

632914970666
632914970667
632914970666
632914970666
632914970666
632914970665
632914970666
632914970666
632914970666
632914970667
632914970667
632914970667
632914970666
632914970667
632914970666
632914970667
632914970667
632914970667
632914970668
632914970667
632914970668
632914970667
632914970667
6...

result:

ok 2000 numbers

Test #38:

score: 0
Accepted
time: 5ms
memory: 3704kb

input:

2000 1999
0 5 4 1 3 4 1 3 1 0 0 1 4 0 3 5 5 2 3 0 5 3 3 4 5 3 5 5 0 3 4 5 4 0 2 0 0 4 0 5 5 2 2 3 5 5 4 0 3 2 2 2 0 4 5 4 2 2 5 1 5 5 1 4 5 2 0 4 3 1 5 4 5 1 0 3 0 5 2 4 3 0 4 1 2 5 4 1 4 4 1 0 4 1 0 3 5 5 5 3 4 5 5 1 5 5 5 0 0 2 5 0 3 3 2 4 2 1 3 5 3 4 2 5 2 3 2 3 4 5 1 1 2 3 4 3 3 4 2 0 4 0 0 2 1 ...

output:

1655
1655
1656
1656
1656
1655
1655
1655
1656
1656
1656
1655
1656
1656
1656
1657
1657
1657
1657
1657
1658
1657
1658
1657
1657
1657
1657
1657
1657
1657
1656
1657
1656
1656
1656
1655
1656
1656
1656
1656
1656
1657
1657
1657
1657
1657
1658
1657
1657
1657
1657
1657
1657
1657
1657
1657
1657
1657
1657
1657
...

result:

ok 1999 numbers

Test #39:

score: 0
Accepted
time: 841ms
memory: 34228kb

input:

200000 200000
1 4 9 4 6 9 5 8 4 7 8 5 8 4 5 0 10 1 2 5 5 6 2 1 2 5 7 7 5 9 6 6 1 4 6 6 4 2 10 9 6 0 9 10 1 5 7 4 7 5 9 10 0 2 6 10 4 3 7 2 7 7 10 0 5 1 2 2 0 8 10 6 7 4 4 10 0 7 0 8 8 8 6 5 6 5 1 5 10 5 9 3 9 3 6 6 7 7 9 7 5 7 0 7 1 3 7 9 5 0 0 9 10 3 5 3 2 1 8 4 1 0 8 5 7 6 1 1 4 5 1 6 5 3 6 1 5 5 ...

output:

332845
332845
332846
332845
332845
332845
332844
332844
332844
332845
332844
332845
332844
332844
332844
332843
332843
332843
332842
332842
332842
332842
332842
332843
332843
332843
332844
332843
332843
332843
332844
332843
332843
332843
332842
332843
332842
332842
332842
332842
332842
332841
332842...

result:

ok 200000 numbers

Test #40:

score: 0
Accepted
time: 790ms
memory: 36404kb

input:

200000 200000
85713646 336686856 538585247 278110438 233218655 716436104 837912968 251689084 911446322 701433421 627692917 334396123 413292301 8832435 188412011 689794769 286917079 209754313 519445483 105763643 27705054 168552468 752722351 829700685 747331109 706042730 418755558 614136831 2655911 80...

output:

33341754832470
33341754832470
33341754832471
33341754832470
33341754832471
33341754832470
33341754832470
33341754832470
33341754832470
33341754832470
33341754832470
33341754832470
33341754832471
33341754832470
33341754832471
33341754832470
33341754832471
33341754832471
33341754832471
33341754832472
...

result:

ok 200000 numbers

Test #41:

score: 0
Accepted
time: 700ms
memory: 34516kb

input:

200000 200000
635910513 530707612 43308926 653927427 953772413 886338816 149455282 24772774 715587632 555119024 702589377 349422399 13059257 305480192 768707679 77455076 588537505 275449414 881106189 997605463 699449988 579049544 439144233 339940611 677203754 952180230 954696649 608213997 944927273 ...

output:

33346597165806
33346597165806
33346597165806
33346597165805
33346597165805
33346597165805
33346597165804
33346597165804
33346597165804
33346597165803
33346597165803
33346597165803
33346597165802
33346597165802
33346597165802
33346597165801
33346597165801
33346597165801
33346597165800
33346597165800
...

result:

ok 200000 numbers

Test #42:

score: 0
Accepted
time: 872ms
memory: 39044kb

input:

200000 200000
323842684 404575711 975846485 26692339 484624497 479820673 79145839 690422479 435950749 721344329 55972947 946532807 537527876 632207792 134109985 92150997 282767325 50309244 942832532 291033288 394196176 355961510 210549616 639079458 254823064 129598231 941770957 38138695 661229827 98...

output:

33357361283426
33357361283426
33357361283427
33357361283427
33357361283427
33357361283428
33357361283428
33357361283428
33357361283429
33357361283429
33357361283429
33357361283430
33357361283430
33357361283430
33357361283431
33357361283431
33357361283431
33357361283432
33357361283432
33357361283432
...

result:

ok 200000 numbers

Test #43:

score: 0
Accepted
time: 945ms
memory: 37476kb

input:

200000 200000
1000000000 1000000000 1000000000 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 999999999 1000000000 999999999 1000000000 1000000000 999999999 999999999 1000000000 1000000000 999999999 1000000000 999999999 1000000000 1000000000 1000000000 1000000000 1000000...

output:

66666666633339
66666666633339
66666666633339
66666666633338
66666666633338
66666666633338
66666666633339
66666666633339
66666666633339
66666666633339
66666666633339
66666666633339
66666666633339
66666666633339
66666666633339
66666666633339
66666666633339
66666666633339
66666666633339
66666666633338
...

result:

ok 200000 numbers

Subtask #5:

score: 0
Skipped

Dependency #1:

0%