結果

問題 No.2338 Range AtCoder Query
ユーザー gew1fw
提出日時 2025-06-12 18:49:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,213 bytes
コンパイル時間 4,244 ms
コンパイル使用メモリ 211,432 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-12 18:50:04
合計ジャッジ時間 13,085 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct SegmentTree {
    int n;
    vector<vector<int>> tree;

    SegmentTree(const vector<int>& ac_p) {
        n = ac_p.size();
        tree.resize(4 * n);
        build(0, 0, n - 1, ac_p);
    }

    void build(int node, int l, int r, const vector<int>& ac_p) {
        if (l == r) {
            if (ac_p[l] != -1) {
                tree[node].push_back(ac_p[l]);
            }
            return;
        }
        int mid = (l + r) / 2;
        build(2*node+1, l, mid, ac_p);
        build(2*node+2, mid+1, r, ac_p);
        tree[node].reserve(tree[2*node+1].size() + tree[2*node+2].size());
        tree[node].insert(tree[node].end(), tree[2*node+1].begin(), tree[2*node+1].end());
        tree[node].insert(tree[node].end(), tree[2*node+2].begin(), tree[2*node+2].end());
    }

    void query(int node, int l, int r, int ql, int qr, vector<int>& res) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            res.insert(res.end(), tree[node].begin(), tree[node].end());
            return;
        }
        int mid = (l + r) / 2;
        query(2*node+1, l, mid, ql, qr, res);
        query(2*node+2, mid+1, r, ql, qr, res);
    }

    vector<int> get_acs(int l, int r) {
        vector<int> res;
        query(0, 0, n-1, l, r, res);
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<int> P(N), S(N); // S[i] is 0 for WA, 1 for AC
    vector<vector<int>> ac(M+1), wa(M+1);
    vector<int> ac_p(N, -1); // for each submission, if AC, p, else -1

    for (int i = 0; i < N; ++i) {
        cin >> P[i];
        string s;
        cin >> s;
        if (s == "AC") {
            S[i] = 1;
            ac[P[i]].push_back(i);
            ac_p[i] = P[i];
        } else {
            S[i] = 0;
            wa[P[i]].push_back(i);
        }
    }

    // Build segment tree
    SegmentTree st(ac_p);

    // Pre-sort the ac and wa lists for each problem
    for (int p = 1; p <= M; ++p) {
        sort(ac[p].begin(), ac[p].end());
        sort(wa[p].begin(), wa[p].end());
    }

    while (Q--) {
        int L, R;
        cin >> L >> R;
        --L; --R; // convert to 0-based

        vector<int> ac_p_list = st.get_acs(L, R);

        vector<bool> visited(M+1, false);
        int correct = 0;
        long long penalty = 0;

        for (int p : ac_p_list) {
            if (visited[p]) continue;
            visited[p] = true;

            // Find first AC in [L, R]
            auto it = lower_bound(ac[p].begin(), ac[p].end(), L);
            if (it == ac[p].end() || *it > R) {
                visited[p] = false;
                continue;
            }
            int first_ac = *it;

            // Count WAs in [L, first_ac -1]
            int cnt = 0;
            if (!wa[p].empty()) {
                auto left = lower_bound(wa[p].begin(), wa[p].end(), L);
                auto right = lower_bound(wa[p].begin(), wa[p].end(), first_ac);
                cnt = right - left;
            }

            penalty += cnt;
            ++correct;
        }

        cout << correct << " " << penalty << "\n";
    }

    return 0;
}
0