結果
問題 | No.2421 entersys? |
ユーザー |
![]() |
提出日時 | 2023-08-12 14:06:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 756 ms / 3,000 ms |
コード長 | 6,389 bytes |
コンパイル時間 | 4,065 ms |
コンパイル使用メモリ | 277,400 KB |
最終ジャッジ日時 | 2025-02-16 04:12:30 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;//* ATCODER#include<atcoder/all>using namespace atcoder;typedef modint998244353 mint;//*//* BOOST MULTIPRECISION#include<boost/multiprecision/cpp_int.hpp>using namespace boost::multiprecision;//*/typedef long long ll;#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)template <typename T> bool chmin(T &a, const T &b) {if (a <= b) return false;a = b;return true;}template <typename T> bool chmax(T &a, const T &b) {if (a >= b) return false;a = b;return true;}template <typename T> T max(vector<T> &a){assert(!a.empty());T ret = a[0];for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);return ret;}template <typename T> T min(vector<T> &a){assert(!a.empty());T ret = a[0];for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);return ret;}template <typename T> T sum(vector<T> &a){T ret = 0;for (int i=0; i<(int)a.size(); i++) ret += a[i];return ret;}// https://lorent-kyopro.hatenablog.com/entry/2021/03/12/025644template <class S, S (*op)(S, S), S (*e)()> class dynamic_segtree {public:dynamic_segtree(size_t n) : n(n), root(nullptr) {}void set(size_t p, S x) {assert(p < n);set(root, 0, n, p, x);}S get(size_t p) const {assert(p < n);return get(root, 0, n, p);}S prod(size_t l, size_t r) const {assert(l <= r && r <= n);return prod(root, 0, n, l, r);}S all_prod() const { return root ? root->product : e(); }void reset(size_t l, size_t r) {assert(l <= r && r <= n);return reset(root, 0, n, l, r);}template <bool (*f)(S)> size_t max_right(size_t l) const {return max_right(l, [](S x) { return f(x); });}template <class F> size_t max_right(size_t l, const F& f) const {assert(l <= n);S product = e();assert(f(product));return max_right(root, 0, n, l, f, product);}template <bool (*f)(S)> size_t min_left(size_t r) const {return min_left(r, [](S x) { return f(x); });}template <class F> size_t min_left(size_t r, const F& f) const {assert(r <= n);S product = e();assert(f(product));return min_left(root, 0, n, r, f, product);}private:struct node;using node_ptr = std::unique_ptr<node>;struct node {size_t index;S value, product;node_ptr left, right;node(size_t index, S value): index(index),value(value),product(value),left(nullptr),right(nullptr) {}void update() {product = op(op(left ? left->product : e(), value),right ? right->product : e());}};const size_t n;node_ptr root;void set(node_ptr& t, size_t a, size_t b, size_t p, S x) const {if (!t) {t = std::make_unique<node>(p, x);return;}if (t->index == p) {t->value = x;t->update();return;}size_t c = (a + b) >> 1;if (p < c) {if (t->index < p) std::swap(t->index, p), std::swap(t->value, x);set(t->left, a, c, p, x);} else {if (p < t->index) std::swap(p, t->index), std::swap(x, t->value);set(t->right, c, b, p, x);}t->update();}S get(const node_ptr& t, size_t a, size_t b, size_t p) const {if (!t) return e();if (t->index == p) return t->value;size_t c = (a + b) >> 1;if (p < c) return get(t->left, a, c, p);else return get(t->right, c, b, p);}S prod(const node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {if (!t || b <= l || r <= a) return e();if (l <= a && b <= r) return t->product;size_t c = (a + b) >> 1;S result = prod(t->left, a, c, l, r);if (l <= t->index && t->index < r) result = op(result, t->value);return op(result, prod(t->right, c, b, l, r));}void reset(node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {if (!t || b <= l || r <= a) return;if (l <= a && b <= r) {t.reset();return;}size_t c = (a + b) >> 1;reset(t->left, a, c, l, r);reset(t->right, c, b, l, r);t->update();}template <class F>size_t max_right(const node_ptr& t, size_t a, size_t b,size_t l, const F& f, S& product) const {if (!t || b <= l) return n;if (f(op(product, t->product))) {product = op(product, t->product);return n;}size_t c = (a + b) >> 1;size_t result = max_right(t->left, a, c, l, f, product);if (result != n) return result;if (l <= t->index) {product = op(product, t->value);if (!f(product)) return t->index;}return max_right(t->right, c, b, l, f, product);}template <class F>size_t min_left(const node_ptr& t, size_t a, size_t b,size_t r, const F& f, S& product) const {if (!t || r <= a) return 0;if (f(op(t->product, product))) {product = op(t->product, product);return 0;}size_t c = (a + b) >> 1;size_t result = min_left(t->right, c, b, r, f, product);if (result != 0) return result;if (t->index < r) {product = op(t->value, product);if (!f(product)) return t->index + 1;}return min_left(t->left, a, c, r, f, product);}};int op(int a, int b){return a + b;}int e(){return 0;}int main(){ios_base::sync_with_stdio(false);cin.tie(NULL);int n, q; cin >> n;dynamic_segtree<int,op,e> seg(1e9+50);vector<map<int,int>> sg(300000);int piv = 0;map<string,int> g;rep(i,0,n){string x;int l, r; cin >> x >> l >> r;if (g.find(x) == g.end()){g[x] = piv;piv++;}seg.set(l, seg.get(l) + 1);seg.set(r+1, seg.get(r+1) - 1);sg[g[x]][l] += 1;sg[g[x]][r+1] += -1;if (sg[g[x]][l] == 0){sg[g[x]].erase(l);}if (sg[g[x]][r+1] == 0){sg[g[x]].erase(r+1);}}cin >> q;rep(i,0,q){int t; cin >> t;if (t == 1){string x; int v; cin >> x >> v;if (g.find(x) == g.end()){g[x] = piv;piv++;}auto k = sg[g[x]].upper_bound(v);if (k == sg[g[x]].begin()){cout << "No\n";continue;}k--;if (k->second == 1){cout << "Yes\n";}else{cout << "No\n";}}else if (t == 2){int v; cin >> v;cout << seg.prod(0, v + 1) << '\n';}else{string x;int l, r; cin >> x >> l >> r;if (g.find(x) == g.end()){g[x] = piv;piv++;}seg.set(l, seg.get(l) + 1);seg.set(r+1, seg.get(r+1) - 1);sg[g[x]][l] += 1;sg[g[x]][r+1] += -1;if (sg[g[x]][l] == 0){sg[g[x]].erase(l);}if (sg[g[x]][r+1] == 0){sg[g[x]].erase(r+1);}}}}