結果

問題 No.2338 Range AtCoder Query
コンテスト
ユーザー sotanishy
提出日時 2023-06-02 22:36:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,597 bytes
コンパイル時間 2,564 ms
コンパイル使用メモリ 214,196 KB
最終ジャッジ日時 2025-02-13 19:31:14
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17 TLE * 17
権限があれば一括ダウンロードができます

ソースコード

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;
};

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); ++i) {
        os << v[i];
        if (i < (int)v.size() - 1) os << " ";
    }
    return os;
}

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), penalty(M);

    int cur_correct = 0, cur_penalty = 0;

    auto exl = [&](int i) {
        int p = P[i];
        if (ac_cnt[p]) --cur_correct;
        cur_penalty -= penalty[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[i]) ++ac_cnt[p];
        if (ac_cnt[p] && !sub[p].front().first) {
            penalty[p] = sub[p].front().second;
        } else {
            penalty[p] = 0;
        }
        if (ac_cnt[p]) ++cur_correct;
        cur_penalty += penalty[p];
    };

    auto shl = [&](int i) {
        int p = P[i];
        if (ac_cnt[p]) --cur_correct;
        cur_penalty -= penalty[p];

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

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

    auto exr = [&](int i) {
        int p = P[i];
        if (ac_cnt[p]) --cur_correct;
        cur_penalty -= penalty[p];

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

        if (ac[i]) ++ac_cnt[p];
        if (ac_cnt[p] && !sub[p].front().first) {
            penalty[p] = sub[p].front().second;
        } else {
            penalty[p] = 0;
        }
        if (ac_cnt[p]) ++cur_correct;
        cur_penalty += penalty[p];
    };

    auto shr = [&](int i) {
        int p = P[i];
        if (ac_cnt[p]) --cur_correct;
        cur_penalty -= penalty[p];

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

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

    auto out = [&](int id) {
        ans_correct[id] = cur_correct;
        ans_penalty[id] = cur_penalty;
    };

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

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