結果

問題 No.2338 Range AtCoder Query
ユーザー sotanishysotanishy
提出日時 2023-06-02 22:24:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,275 bytes
コンパイル時間 2,789 ms
コンパイル使用メモリ 217,460 KB
実行使用メモリ 84,316 KB
最終ジャッジ日時 2023-08-28 04:15:00
合計ジャッジ時間 9,843 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
    return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
    return a > b ? (a = b, 1) : 0;
}

class Mo {
   public:
    Mo() = default;
    explicit Mo(int n) : n(n), cnt(0) {}

    void query(int l, int r) { queries.emplace_back(cnt++, l, r); }

    template <typename ExL, typename ShL, typename ExR, typename ShR,
              typename Out>
    void run(ExL exl, ShL shl, ExR exr, ShR shr, Out out) {
        int s = sqrt(n);
        std::sort(queries.begin(), queries.end(),
                  [&](const auto& a, const auto& b) {
                      if (a.l / s != b.l / s) return a.l < b.l;
                      return a.r < b.r;
                  });
        int curL = 0, curR = 0;
        for (auto [id, l, r] : queries) {
            while (curL > l) exl(--curL);
            while (curR < r) exr(curR++);
            while (curL < l) shl(curL++);
            while (curR > r) shr(--curR);
            out(id);
        }
    }

   private:
    struct Query {
        int id, l, r;
        Query(int id, int l, int r) : id(id), l(l), r(r) {}
    };

    int n, cnt;
    std::vector<Query> queries;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> P(N);
    vector<bool> ac(N);
    rep(i, 0, N) {
        int p;
        string s;
        cin >> p >> s;
        --p;
        P[i] = p;
        ac[i] = s == "AC";
    }

    Mo mo(N);
    vector<int> ans_correct(Q), ans_penalty(Q);

    rep(_, 0, Q) {
        int l, r;
        cin >> l >> r;
        --l;
        mo.query(l, r);
    }

    vector<deque<pair<bool, int>>> sub(M);

    vector<int> ac_cnt(M);

    int correct = 0, penalty = 0;

    auto exl = [&](int i) {
        int p = P[i];

        if (ac_cnt[p] && !sub[p].empty() && !sub[p].front().first) {
            penalty -= sub[p].front().second;
        }
        if (ac[i]) {
            if (ac_cnt[p] == 0) {
                ++correct;
            }
            ++ac_cnt[p];
        }

        if (!sub[p].empty() && sub[p].front().first == ac[i]) {
            sub[p].front().second++;
        } else {
            sub[p].push_front({ac[i], 1});
        }

        if (ac_cnt[p] && !sub[p].empty() && !sub[p].front().first) {
            penalty += sub[p].front().second;
        }
    };

    auto shl = [&](int i) {
        int p = P[i];
        if (!sub[p].front().first) {
            penalty -= sub[p].front().second;
        }

        sub[p].front().second--;
        if (sub[p].front().second == 0) sub[p].pop_front();

        if (ac[i]) {
            --ac_cnt[p];
            if (ac_cnt[p] == 0) {
                --correct;
            }
        }
        if (!sub[p].empty() && !sub[p].front().first) {
            penalty += sub[p].front().second;
        }
    };

    auto exr = [&](int i) {
        int p = P[i];

        if (ac[i]) {
            if (ac_cnt[p] == 0) {
                ++correct;
            }
            ++ac_cnt[p];
            if (sub[p].size() == 1 && !sub[p].front().first) {
                penalty += sub[p].front().second;
            }
        }

        if (!sub[p].empty() && sub[p].back().first == ac[i]) {
            sub[p].back().second++;
        } else {
            sub[p].push_back({ac[i], 1});
        }
    };

    auto shr = [&](int i) {
        int p = P[i];

        sub[p].back().second--;
        if (sub[p].back().second == 0) sub[p].pop_back();

        if (ac[i]) {
            --ac_cnt[p];
            if (ac_cnt[p] == 0) {
                --correct;
                if (!sub[p].empty() && !sub[p].front().first) {
                    penalty -= sub[p].front().second;
                }
            }
        }
    };

    auto out = [&](int id) {
        ans_correct[id] = correct;
        ans_penalty[id] = penalty;
    };

    mo.run(exl, shl, exr, shr, out);

    rep(i, 0, Q) { cout << ans_correct[i] << " " << ans_penalty[i] << "\n"; }
}
0