結果

問題 No.2338 Range AtCoder Query
ユーザー sotanishysotanishy
提出日時 2023-06-02 22:44:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,684 bytes
コンパイル時間 2,940 ms
コンパイル使用メモリ 217,840 KB
実行使用メモリ 83,748 KB
最終ジャッジ日時 2023-08-28 04:57:56
合計ジャッジ時間 10,402 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 4 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
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 nbucket = std::max(1, (int)std::sqrt(queries.size()));
        int s = (n + nbucket - 1) / nbucket;
        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