結果
問題 | No.2421 entersys? |
ユーザー |
![]() |
提出日時 | 2023-08-12 15:04:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 794 ms / 3,000 ms |
コード長 | 3,521 bytes |
コンパイル時間 | 4,592 ms |
コンパイル使用メモリ | 284,516 KB |
最終ジャッジ日時 | 2025-02-16 05:40:31 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using P = pair<ll, ll>;using T = tuple<ll, string, ll, ll, ll>;#include <atcoder/all>using namespace atcoder;// using mint = modint1000000007;#define rep(i, n) for(ll i = 0; i < n; i++)// S が data, F が lazyusing S = ll;using F = ll;// operator(作用素)S op(S a,S b){return a+b;}// 遅延データ反映S mapping(F f,S x){return f+x;}// 遅延データ作用F composition(F f,F g){return f+g;}S e(){ return 0; } // 単位元 (op(e, a) = op(a, e) = a)F id(){ return 0; } // mapping(id, a) = aint main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);ll n; cin >> n;vector<ll> comp;map<string,set<ll>> nyu, tai;vector<P> kukan;rep(i,n) {string x; ll l,r; cin >> x >> l >> r;nyu[x].insert(l);tai[x].insert(r);comp.push_back(l);comp.push_back(r);kukan.push_back(P(l,r));}ll q; cin >> q;vector<T> query(q);rep(i,q) {ll qq; cin >> qq;if( qq == 1 ) {string x; ll t; cin >> x >> t;query[i] = T(qq,x,-1,-1,t);comp.push_back(t);}else if( qq == 2 ) {ll t; cin >> t;query[i] = T(qq,"",-1,-1,t);comp.push_back(t);}else {string x; ll l,r; cin >> x >> l >> r;query[i] = T(qq,x,l,r,-1);comp.push_back(l);comp.push_back(r);}}sort(comp.begin(),comp.end());comp.erase( unique(comp.begin(),comp.end()), comp.end() );lazy_segtree<S,op,e,F,mapping,composition,id> lsg(comp.size());rep(i,kukan.size()) {auto &&[l,r] = kukan[i];ll i1 = lower_bound(comp.begin(), comp.end(), l) - comp.begin();ll i2 = lower_bound(comp.begin(), comp.end(), r) - comp.begin();lsg.apply(i1,i2+1,1);}rep(i,q) {auto &&[qq,x,l,r,t] = query[i];if( qq == 1 ) {auto itr1 = nyu[x].upper_bound(t);if( itr1 == nyu[x].begin() ) {cout << "No" << endl;continue;}itr1--;auto itr2 = tai[x].upper_bound(*itr1);if( itr2 == tai[x].end() || *itr2 < t ) cout << "No" << endl;else cout << "Yes" << endl;}else if( qq == 2 ) {ll i = lower_bound(comp.begin(), comp.end(), t) - comp.begin();// cout << i << " " << comp.size() << endl << flush;cout << lsg.get(i) << endl;}else {// cout << "Yeah!" << endl << flush;ll i1 = lower_bound(comp.begin(), comp.end(), l) - comp.begin();ll i2 = lower_bound(comp.begin(), comp.end(), r) - comp.begin();// cout << i1 << " " << i2 << endl << flush;lsg.apply(i1,i2+1,1);if( tai[x].count(l) && nyu[x].count(r) ) {tai[x].erase(tai[x].find(l));nyu[x].erase(nyu[x].find(r));}else if( tai[x].count(l) && !nyu[x].count(r) ) {tai[x].erase(tai[x].find(l));tai[x].insert(r);}else if( !tai[x].count(l) && nyu[x].count(r) ) {nyu[x].erase(tai[x].find(r));nyu[x].insert(l);}else {nyu[x].insert(l);tai[x].insert(r);}}}return 0;}