結果
問題 | No.2338 Range AtCoder Query |
ユーザー | KumaTachiRen |
提出日時 | 2023-06-02 22:32:11 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,649 bytes |
コンパイル時間 | 6,199 ms |
コンパイル使用メモリ | 327,372 KB |
実行使用メモリ | 253,276 KB |
最終ジャッジ日時 | 2024-06-09 00:03:31 |
合計ジャッジ時間 | 16,286 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 251 ms
244,556 KB |
testcase_01 | AC | 255 ms
243,372 KB |
testcase_02 | AC | 253 ms
243,008 KB |
testcase_03 | AC | 253 ms
242,996 KB |
testcase_04 | AC | 257 ms
243,972 KB |
testcase_05 | AC | 257 ms
243,000 KB |
testcase_06 | AC | 382 ms
243,648 KB |
testcase_07 | AC | 385 ms
243,232 KB |
testcase_08 | AC | 382 ms
242,608 KB |
testcase_09 | AC | 257 ms
243,388 KB |
testcase_10 | AC | 376 ms
242,720 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 | -- | - |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; struct Fast { Fast() { std::cin.tie(0); 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 long template <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; } // https://ei1333.hateblo.jp/entry/2017/09/11/211011 struct Mo { int n; vector<pair<int, int>> lr; explicit Mo(int n) : n(n) {} void add(int l, int r) { /* [l, r) */ lr.emplace_back(l, r); } template <typename AL, typename AR, typename EL, typename ER, typename O> void build(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) { int q = (int)lr.size(); int bs = (int)(sqrt(3) * n / min<int>(sqrt(3) * n, sqrt(2 * q))); vector<int> ord(q); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), [&](int a, int b) { int ablock = lr[a].first / bs, bblock = lr[b].first / bs; if(ablock != bblock) return ablock < bblock; return (ablock & 1) ? lr[a].second > lr[b].second : lr[a].second < lr[b].second; }); int l = 0, r = 0; for (auto idx : ord) { while (l > lr[idx].first) add_left(--l); while (r < lr[idx].second) add_right(r++); while (l < lr[idx].first) erase_left(l++); while (r > lr[idx].second) erase_right(--r); out(idx); } } template <typename A, typename E, typename O> void build(const A &add, const E &erase, const O &out) { build(add, add, erase, erase, out); } }; const int sz = 200000; int p[sz], ac[sz], point[sz], pena[sz], accnt[sz]; deque<int> wadeq[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"; } Mo mo(n); rep(i, 0, q) { int l, r; cin >> l >> r; mo.add(l - 1, r); } rep(i, 0, sz) wadeq[i] = {0}; int pt = 0, pn = 0; auto add_left = [&](int i) { int x = p[i]; if (ac[i]) { if (accnt[x]++ == 0) { pt++; } else { pn -= wadeq[x].front(); } wadeq[x].push_front(0); } else { if (accnt[x]) { pn++; } wadeq[x].front()++; } }; auto add_right = [&](int i) { int x = p[i]; if (ac[i]) { if (accnt[x]++ == 0) { pt++; pn += wadeq[x].front(); } wadeq[x].push_back(0); } else { wadeq[x].back()++; } }; auto erase_left = [&](int i) { int x = p[i]; if (ac[i]) { wadeq[x].pop_front(); if (--accnt[x] == 0) { pt--; } else { pn += wadeq[x].front(); } } else { if (accnt[x]) { pn--; } wadeq[x].front()--; } }; auto erase_right = [&](int i) { int x = p[i]; if (ac[i]) { wadeq[x].pop_back(); if (--accnt[x] == 0) { pt--; pn -= wadeq[x].front(); } } else { wadeq[x].back()--; } }; auto out = [&](int i) { point[i] = pt; pena[i] = pn; }; mo.build(add_left, add_right, erase_left, erase_right, out); rep(i, 0, q) cout << point[i] << " " << pena[i] << "\n"; }