結果
問題 | No.2338 Range AtCoder Query |
ユーザー |
|
提出日時 | 2023-06-02 23:23:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 770 ms / 4,000 ms |
コード長 | 4,106 bytes |
コンパイル時間 | 4,584 ms |
コンパイル使用メモリ | 257,720 KB |
最終ジャッジ日時 | 2025-02-13 20:45:59 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;struct Fast{Fast(){std::cin.tie(nullptr);ios::sync_with_stdio(false);}} fast;#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";#define ll long longtemplate <typename T>bool chmax(T &a, const T &b){if (a < b){a = b;return true;}return false;}template <typename T>bool chmin(T &a, const T &b){if (a > b){a = b;return true;}return false;}struct Mo{int width;vector<int> left, right, order;Mo(int N, int Q) : order(Q){width = max<int>(1, 1.0 * N / max<double>(1.0, sqrt(Q * 2.0 / 3.0)));iota(begin(order), end(order), 0);}void insert(int l, int r){ /* [l, r) */left.emplace_back(l);right.emplace_back(r);}template <typename AL, typename AR, typename DL, typename DR, typename REM>void run(const AL &add_left, const AR &add_right, const DL &delete_left,const DR &delete_right, const REM &rem){assert(left.size() == order.size());sort(begin(order), end(order), [&](int a, int b){int ablock = left[a] / width, bblock = left[b] / width;if (ablock != bblock) return ablock < bblock;if (ablock & 1) return right[a] < right[b];return right[a] > right[b]; });int nl = 0, nr = 0;for (auto idx : order){while (nl > left[idx])add_left(--nl);while (nr < right[idx])add_right(nr++);while (nl < left[idx])delete_left(nl++);while (nr > right[idx])delete_right(--nr);rem(idx);}}};const int sz = 200000;int p[sz], ac[sz], point[sz], pena[sz], accnt[sz], wacntl[sz], wacntr[sz];int waprv[sz], wanxt[sz];int main(){int n, m, q;cin >> n >> m >> q;rep(i, 0, n){string s = "";cin >> p[i] >> s;p[i]--;ac[i] = s == "AC";}rep(i, 0, n){if (ac[i]){waprv[i] = wacntl[p[i]];wacntl[p[i]] = 0;}else{wacntl[p[i]]++;}}rep(i, 0, sz) wacntl[i] = 0;rrep(i, 0, n){if (ac[i]){wanxt[i] = wacntr[p[i]];wacntr[p[i]] = 0;}else{wacntr[p[i]]++;}}rep(i, 0, sz) wacntr[i] = 0;Mo mo(n, q);rep(i, 0, q){int l, r;cin >> l >> r;mo.insert(l - 1, r);}int pt = 0, pn = 0;auto add_left = [&](int i){int x = p[i];if (ac[i]){if (accnt[x]++ == 0){pt++;}else{pn -= wacntl[x];}wacntl[x] = 0;}else{if (accnt[x]){pn++;}else{wacntr[x]++;}wacntl[x]++;}};auto add_right = [&](int i){int x = p[i];if (ac[i]){if (accnt[x]++ == 0){pt++;pn += wacntl[x];}wacntr[x] = 0;}else{if (accnt[x] == 0){wacntl[x]++;}wacntr[x]++;}};auto erase_left = [&](int i){int x = p[i];if (ac[i]){if (--accnt[x] == 0){pt--;wacntl[x] = wacntr[x];}else{wacntl[x] = wanxt[i];pn += wacntl[x];}}else{wacntl[x]--;if (accnt[x]){pn--;}else{wacntr[x]--;}}};auto erase_right = [&](int i){int x = p[i];if (ac[i]){if (--accnt[x] == 0){pt--;pn -= wacntl[x];wacntr[x] = wacntl[x];}else{wacntr[x] = waprv[i];}}else{wacntr[x]--;if (accnt[x] == 0){wacntl[x]--;}}};auto out = [&](int i){point[i] = pt;pena[i] = pn;};mo.run(add_left, add_right, erase_left, erase_right, out);rep(i, 0, q) cout << point[i] << " " << pena[i] << "\n";}