結果
問題 | No.2421 entersys? |
ユーザー |
![]() |
提出日時 | 2023-08-12 18:02:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 698 ms / 3,000 ms |
コード長 | 3,295 bytes |
コンパイル時間 | 5,536 ms |
コンパイル使用メモリ | 272,528 KB |
最終ジャッジ日時 | 2025-02-16 07:26:50 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;using ll = long long;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;using VD = vector<double>;using VVD = vector<VD>;using VS = vector<string>;using P = pair<ll,ll>;using VP = vector<P>;#define rep(i, n) for (ll i = 0; i < ll(n); i++)#define out(x) cout << x << endl#define dout(x) cout << fixed << setprecision(10) << x << endl#define all(a) (a).begin(),(a).end()#define rall(a) (a).rbegin(),(a).rend()#define sz(x) (int)(x.size())#define re0 return 0#define pcnt __builtin_popcountlltemplate<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }constexpr int inf = 1e9;constexpr ll INF = 1e18;//using mint = modint1000000007;using mint = modint998244353;int di[4] = {1,0,-1,0};int dj[4] = {0,1,0,-1};// Coodinate Compression// https://youtu.be/fR3W5IcBGLQ?t=8550template<typename T=int>struct CC {bool initialized;vector<T> xs;CC(): initialized(false) {}void add(T x) { xs.push_back(x);}void init() {sort(xs.begin(), xs.end());xs.erase(unique(xs.begin(),xs.end()),xs.end());initialized = true;}int operator()(T x) {if (!initialized) init();return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;}T operator[](int i) {if (!initialized) init();return xs[i];}int size() {if (!initialized) init();return xs.size();}};int main(){ll n;cin >> n;CC cc;VL l(n),r(n);VS x(n);map<string,set<P>> mp;rep(i,n){cin >> x[i] >> l[i] >> r[i];cc.add(l[i]);cc.add(r[i]);}ll q;cin >> q;VL type(q),lq(q),rq(q),tq(q);VS xq(q);rep(i,q){cin >> type[i];if(type[i] == 1){cin >> xq[i] >> tq[i];cc.add(tq[i]);}if(type[i] == 2){cin >> tq[i];cc.add(tq[i]);}if(type[i] == 3){cin >> xq[i] >> lq[i] >> rq[i];cc.add(lq[i]);cc.add(rq[i]);}}cc.add(0);cc.init();rep(i,n){l[i] = cc(l[i]);r[i] = cc(r[i]);}rep(i,q){tq[i] = cc(tq[i]);lq[i] = cc(lq[i]);rq[i] = cc(rq[i]);}fenwick_tree<ll> fw(400400);rep(i,n){fw.add(l[i],1);fw.add(r[i]+1,-1);mp[x[i]].insert(P(l[i],r[i]));}rep(i,q){if(type[i] == 1){P tmp = P(tq[i],INF);auto tmp2 = mp[xq[i]].upper_bound(tmp);if(tmp2 == mp[xq[i]].begin()){out("No");} else {tmp2 = prev(tmp2);auto [l,r] = *tmp2;if(l <= tq[i] && tq[i] <= r){out("Yes");} else {out("No");}}}if(type[i] == 2){ll ans = fw.sum(0,tq[i]+1);out(ans);}if(type[i] == 3){fw.add(lq[i],1);fw.add(rq[i]+1,-1);mp[xq[i]].insert(P(lq[i],rq[i]));}}}