結果

問題 No.2338 Range AtCoder Query
コンテスト
ユーザー hitonanode
提出日時 2023-06-02 22:40:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,059 bytes
コンパイル時間 1,846 ms
コンパイル使用メモリ 131,988 KB
実行使用メモリ 19,692 KB
最終ジャッジ日時 2024-12-28 20:35:55
合計ジャッジ時間 77,560 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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';
}
0