結果
問題 | No.2338 Range AtCoder Query |
ユーザー |
![]() |
提出日時 | 2022-08-22 18:41:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 280 ms / 4,000 ms |
コード長 | 7,201 bytes |
コンパイル時間 | 1,553 ms |
コンパイル使用メモリ | 133,792 KB |
最終ジャッジ日時 | 2025-01-31 02:50:23 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 34 |
ソースコード
#ifndef LOCAL#define FAST_IO#endif// ===== template.hpp =====#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cmath>#include <iomanip>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define OVERRIDE(a, b, c, d, ...) d#define REP2(i, n) for (i32 i = 0; i < (i32) (n); ++i)#define REP3(i, m, n) for (i32 i = (i32) (m); i < (i32) (n); ++i)#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)#define PER(i, n) for (i32 i = (i32) (n) - 1; i >= 0; --i)#define ALL(x) begin(x), end(x)using namespace std;using u32 = unsigned int;using u64 = unsigned long long;using u128 = __uint128_t;using i32 = signed int;using i64 = signed long long;using i128 = __int128_t;using f64 = double;using f80 = long double;template <typename T>using Vec = vector<T>;template <typename T>bool chmin(T &x, const T &y) {if (x > y) {x = y;return true;}return false;}template <typename T>bool chmax(T &x, const T &y) {if (x < y) {x = y;return true;}return false;}istream &operator>>(istream &is, i128 &x) {i64 v;is >> v;x = v;return is;}ostream &operator<<(ostream &os, i128 x) {os << (i64) x;return os;}istream &operator>>(istream &is, u128 &x) {u64 v;is >> v;x = v;return is;}ostream &operator<<(ostream &os, u128 x) {os << (u64) x;return os;}[[maybe_unused]] constexpr i32 INF = 1000000100;[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;struct SetUpIO {SetUpIO() {#ifdef FAST_IOios::sync_with_stdio(false);cin.tie(nullptr);#endifcout << fixed << setprecision(15);}} set_up_io;// ===== template.hpp =====#ifdef DEBUGF#include "cpl/template/debug.hpp"#else#define DBG(x) (void) 0#endif// ===== fenwick_tree.hpp =====#include <cassert>#include <vector>// ===== operations.hpp =====#include <limits>#include <utility>template <typename T>struct Add {using Value = T;static Value id() {return T(0);}static Value op(const Value &lhs, const Value &rhs) {return lhs + rhs;}static Value inv(const Value &x) {return -x;}};template <typename T>struct Mul {using Value = T;static Value id() {return Value(1);}static Value op(const Value &lhs, const Value &rhs) {return lhs * rhs;}static Value inv(const Value &x) {return Value(1) / x;}};template <typename T>struct Min {using Value = T;static Value id() {return std::numeric_limits<T>::max();}static Value op(const Value &lhs, const Value &rhs) {return std::min(lhs, rhs);}};template <typename T>struct Max {using Value = T;static Value id() {return std::numeric_limits<Value>::min();}static Value op(const Value &lhs, const Value &rhs) {return std::max(lhs, rhs);}};template <typename T>struct Xor {using Value = T;static Value id() {return T(0);}static Value op(const Value &lhs, const Value &rhs) {return lhs ^ rhs;}static Value inv(const Value &x) {return x;}};template <typename Monoid>struct Reversible {using Value = std::pair<typename Monoid::Value, typename Monoid::Value>;static Value id() {return Value(Monoid::id(), Monoid::id());}static Value op(const Value &v1, const Value &v2) {return Value(Monoid::op(v1.first, v2.first),Monoid::op(v2.second, v1.second));}};// ===== operations.hpp =====template <typename CommutativeGroup>class FenwickTree {public:using Value = typename CommutativeGroup::Value;private:std::vector<Value> data;public:FenwickTree(int n) : data(n, CommutativeGroup::id()) {}void add(int idx, const Value &x) {assert(idx >= 0 && idx < (int) data.size());for (; idx < (int) data.size(); idx |= idx + 1) {data[idx] = CommutativeGroup::op(data[idx], x);}}Value sum(int r) const {assert(r >= 0 && r <= (int) data.size());Value ret = CommutativeGroup::id();for (; r > 0; r &= r - 1) {ret = CommutativeGroup::op(ret, data[r - 1]);}return ret;}Value sum(int l, int r) const {assert(l >= 0 && l <= r && r <= (int) data.size());return CommutativeGroup::op(sum(r), CommutativeGroup::inv(sum(l)));}};template <typename T>using FenwickTreeAdd = FenwickTree<Add<T>>;// ===== fenwick_tree.hpp =====class OfflineRectangleAddPointGet {i32 n;Vec<Vec<pair<i32, i32>>> add, sub;i32 q;Vec<Vec<pair<i32, i32>>> queries;public:OfflineRectangleAddPointGet(i32 n) : n(n), add(n + 1), sub(n + 1), q(0), queries(n) {}void add_rect(i32 xl, i32 xr, i32 yl, i32 yr) {assert(0 <= xl && xl <= xr && xr <= n);assert(0 <= yl && yl <= yr && yr <= n);add[xl].emplace_back(yl, yr);sub[xr].emplace_back(yl, yr);}void add_query(i32 x, i32 y) {assert(0 <= x && x < n);assert(0 <= y && y < n);queries[x].emplace_back(y, q++);}Vec<i32> solve() const {FenwickTreeAdd<i32> fw(n + 1);Vec<i32> ans(q, 0);REP(i, n) {for (auto [l, r] : add[i]) {fw.add(l, 1);fw.add(r, -1);}for (auto [l, r] : sub[i]) {fw.add(l, -1);fw.add(r, 1);}for (auto [y, qi] : queries[i]) {ans[qi] = fw.sum(y + 1);}}return ans;}};int main() {i32 n, m, q;cin >> n >> m >> q;Vec<i32> p(n);Vec<i32> is_ac(n);REP(i, n) {cin >> p[i];--p[i];string res;cin >> res;is_ac[i] = (i32) (res == "AC");}Vec<i32> l(q), r(q);REP(i, q) {cin >> l[i] >> r[i];--l[i];}Vec<i32> prev_ac(n, -1), next_ac(n, n);{Vec<i32> pv(m, -1);REP(i, n) {prev_ac[i] = pv[p[i]];if (is_ac[i]) {pv[p[i]] = i;}}}{Vec<i32> nt(m, n);PER(i, n) {next_ac[i] = nt[p[i]];if (is_ac[i]) {nt[p[i]] = i;}}}OfflineRectangleAddPointGet ac(n + 1), pena(n + 1);REP(i, n) {if (is_ac[i]) {ac.add_rect(prev_ac[i] + 1, i + 1, i + 1, n + 1);} else {pena.add_rect(prev_ac[i] + 1, i + 1, next_ac[i] + 1, n + 1);}}REP(i, q) {ac.add_query(l[i], r[i]);pena.add_query(l[i], r[i]);}Vec<i32> acc = ac.solve(), penac = pena.solve();REP(i, q) {cout << acc[i] << ' ' << penac[i] << '\n';}}