結果

問題 No.2338 Range AtCoder Query
コンテスト
ユーザー otogawa
提出日時 2025-04-22 03:11:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,212 ms / 4,000 ms
コード長 3,739 bytes
コンパイル時間 2,148 ms
コンパイル使用メモリ 213,548 KB
実行使用メモリ 44,712 KB
最終ジャッジ日時 2025-04-22 03:12:01
合計ジャッジ時間 31,626 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> p(n), s(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i]; --p[i];
        string x; cin >> x;
        s[i] = (x == "AC");
    }

    vector<vector<int>> ind(m);
    vector<int> rev(n);
    for (int i = 0; i < n; i++) {
        rev[i] = ind[p[i]].size();
        ind[p[i]].push_back(i);
    }

    vector<tuple<int, int, int>> queries(q);
    int idx = 0;
    for (auto &[l, r, id] : queries) {
        cin >> l >> r; --l;
        id = idx++;
    }
    const int SQ = sqrt(n);
    sort(queries.begin(), queries.end(), [&](auto &a, auto &b) {
        if (get<0>(a) / SQ != get<0>(b) / SQ) return get<0>(a) < get<0>(b);
        if ((get<0>(a) / SQ) & 1) return get<1>(a) > get<1>(b);
        else return get<1>(a) < get<1>(b);
    });

    vector<int> acs(q), penalty(q);
    vector<int> ptl(m), ptr(m, 0);
    int tot_ac = 0, tot_penalty = 0;

    vector<vector<int>> cnt_ac(m), prox_ac(m);
    vector<int> cur_penalty(m);
    for (int c = 0; c < m; c++) {
        auto &ac = cnt_ac[c];
        ac = ind[c];
        for (auto &i : ac) i = s[i];
        ac.push_back(0);
        for (int i = ac.size() - 2; i >= 0; --i)
            ac[i] += ac[i + 1];

        auto &prox = prox_ac[c];
        prox.resize(ind[c].size());
        int nxt = -1;
        for (int i = prox.size() - 1; i >= 0; --i) {
            int j = ind[c][i];
            prox[i] = nxt;
            if (s[j]) nxt = i;
        }
    }

    auto insert = [&] (int i) {
        //cout << "insert " << i << endl;
        int c = p[i];
        int& pen = cur_penalty[c];
        int id_i = rev[i];
        int tem_ac = cnt_ac[c][ptl[c]] - cnt_ac[c][ptr[c]];

        if (ptl[c] == ptr[c]) {
            ptl[c] = ptr[c] = id_i;
        }

        tot_penalty -= pen;

        if (ptr[c] == id_i) {
            if (!tem_ac && s[i]) {
                tot_ac++;
                pen = ptr[c] - ptl[c];
            }

            ptr[c]++;
        } else {
            assert(id_i + 1 == ptl[c]);

            if (!s[i]) {
                if (tem_ac) pen++;
            } else {
                if (!tem_ac) tot_ac++;
                pen = 0;
            }

            ptl[c]--;
        }

        tot_penalty += pen;

        //cout << "? tot_ac = " << tot_ac << " tot_penalty = " << tot_penalty << endl;
    };
    auto erase = [&] (int i) {
        //cout << "erase " << i << endl;

        int c = p[i];
        int& pen = cur_penalty[c];
        int id_i = rev[i];
        int tem_ac = cnt_ac[c][ptl[c]] - cnt_ac[c][ptr[c]];

        tot_penalty -= pen;
        if (ptl[c] == id_i) {
            if (s[i]) {
                if (tem_ac == 1) pen = 0, --tot_ac;
                else {
                    int nxt = prox_ac[c][id_i];
                    assert(~nxt);

                    pen = nxt - id_i - 1;
                }
            } else {
                if (tem_ac) pen--;
            }

            ptl[c]++;
        } else {
            assert(id_i + 1 == ptr[c]);

            if (s[i] && tem_ac == 1) pen = 0, --tot_ac;

            ptr[c]--;
        }

        tot_penalty += pen;

        //cout << "? tot_ac = " << tot_ac << " tot_penalty = " << tot_penalty << endl;
    };

    int l = 0, r = 0;
    for (auto [lx, rx, id] : queries) {
        while (lx < l) insert(--l);
        while (r < rx) insert(r++);
        while (rx < r) erase(--r);
        while (l < lx) erase(l++);
        //cout << "responde " << lx << " " << rx << endl;
        acs[id] = tot_ac;
        penalty[id] = tot_penalty;
    }

    for (int i = 0; i < q; i++) {
        cout << acs[i] << " " << penalty[i] << endl;
    }
}
0