#877315 (C++23) No.2338 Range AtCoder Query

提出ソース

結果

問題	No.2338 Range AtCoder Query
ユーザー	hitonanode
提出日時	2023-06-02 22:40:28
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,059 bytes
コンパイル時間	2,068 ms
コンパイル使用メモリ	132,052 KB
実行使用メモリ	23,796 KB
最終ジャッジ日時	2024-06-09 00:22:35
合計ジャッジ時間	26,037 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 23,796 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	3 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	4 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	3,158 ms 13,860 KB
testcase_12	AC	3,043 ms 14,088 KB
testcase_13	AC	3,476 ms 14,108 KB
testcase_14	AC	3,139 ms 13,800 KB
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <iostream>
#include <list>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

// Mo's algorithm
// - add_range(l, r) : Add [l, r) as query.
// - run(Add, Remove, Query) : run Mo's algorithm.
//   - Add(i) : Add i-th element ([i + 1, r) -> [i, r)).
//   - Remove(i) : Remove i-th element (Inverse of Add(i)).
//   - Query(q) : Solve q-th problem.
// Veirfied: https://codeforces.com/contest/375/submission/114665433
class MosAlgorithm {
    static const int INF = 1 << 30;
    int nmin, nmax;

public:
    std::vector<std::pair<int, int>> ranges;
    MosAlgorithm() : nmin(INF), nmax(-INF) {}

    void add_range(int l, int r) {
        assert(l <= r);
        nmin = std::min(nmin, l);
        nmax = std::max(nmax, r);
        ranges.emplace_back(l, r);
    }
    template <typename F1, typename F2, typename F3, typename F4, typename F5>
    void run(F1 AddRight, F2 AddLeft, F3 RemoveRight, F4 RemoveLeft, F5 Query) {
        const int Q = ranges.size();
        if (!Q) return;
        const int nbbucket = std::max(1, std::min<int>(nmax - nmin, sqrt(Q)));
        const int szbucket = (nmax - nmin + nbbucket - 1) / nbbucket;
        std::vector<int> qs(Q);
        std::iota(qs.begin(), qs.end(), 0);
        std::sort(qs.begin(), qs.end(), [&](int q1, int q2) {
            int b1 = (ranges[q1].first - nmin) / szbucket, b2 = (ranges[q2].first - nmin) / szbucket;
            if (b1 != b2)
                return b1 < b2;
            else {
                return (b1 & 1) ? (ranges[q1].second > ranges[q2].second)
                                : (ranges[q1].second < ranges[q2].second);
            }
        });

        int l = ranges[qs[0]].first, r = l;
        for (auto q : qs) {
            while (r < ranges[q].second) AddRight(r++);
            while (l > ranges[q].first) AddLeft(--l);
            while (r > ranges[q].second) RemoveRight(--r);
            while (l < ranges[q].first) RemoveLeft(l++);
            assert(l == ranges[q].first and r == ranges[q].second);
            Query(q);
        }
    }
    template <typename F1, typename F3, typename F5> void run(F1 Add, F3 Remove, F5 Query) {
        run(Add, Add, Remove, Remove, Query);
    }
};

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> P(N), status(N);
    REP(i, N) {
        cin >> P.at(i);
        --P.at(i);
        string str;
        cin >> str;
        status.at(i) = (str == "AC");
    }

    vector<pair<int, int>> ret(Q);
    int ret_ac = 0, ret_penalty = 0;

    vector<list<pair<int, bool>>> deq(M);

    auto solve = [&](int q) { ret.at(q) = make_pair(ret_ac, ret_penalty); };

    auto precalc = [&](int m) {
        if (!deq.at(m).empty() and deq.at(m).front().second) {
            --ret_ac;
            ret_penalty -= deq.at(m).front().first;
        }
    };

    auto calc = [&](int m) {
        if (!deq.at(m).empty() and deq.at(m).front().second) {
            ret_ac++;
            ret_penalty += deq.at(m).front().first;
        }
    };

    auto add_left = [&](int i) {
        int m = P.at(i), s = status.at(i);
        precalc(m);

        if (s) {
            deq.at(m).emplace_front(0, 1);
        } else {
            if (deq.at(m).empty()) {
                deq.at(m).emplace_front(1, 0);
            } else {
                deq.at(m).front().first++;
            }
        }
        calc(m);
    };

    auto add_right = [&](int i) {
        int m = P.at(i), s = status.at(i);
        precalc(m);

        if (s) {
            if (deq.at(m).empty() or deq.at(m).back().second) {
                deq.at(m).emplace_back(0, 1);
            } else {
                deq.at(m).back().second = 1;
            }
        } else {
            if (deq.at(m).empty() or deq.at(m).back().second) {
                deq.at(m).emplace_back(1, 0);
            } else {
                deq.at(m).back().first++;
            }
        }
        calc(m);
    };

    auto remove_left = [&](int i) {
        int m = P.at(i), s = status.at(i);
        precalc(m);

        if (s) {
            deq.at(m).pop_front();
        } else {
            deq.at(m).front().first--;
            // if (!deq.at(m).front().first and !deq.at(m).front().second) deq.at(m).pop_front();
        }
        calc(m);
    };

    auto remove_right = [&](int i) {
        int m = P.at(i), s = status.at(i);
        precalc(m);

        if (s) {
            deq.at(m).back().second = 0;
        } else {
            deq.at(m).back().first--;
        }
        if (!deq.at(m).back().first) deq.at(m).pop_back();
        calc(m);
    };

    MosAlgorithm mo;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l;
        mo.add_range(l, r);
    }
    mo.run(add_right, add_left, remove_right, remove_left, solve);

    for (auto [x, y] : ret) cout << x << ' ' << y << '\n';
}

yukicoder

結果

テストケース

ソースコード