結果
問題 | No.2421 entersys? |
ユーザー | arad |
提出日時 | 2023-08-12 18:02:18 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 657 ms / 3,000 ms |
コード長 | 3,295 bytes |
コンパイル時間 | 4,871 ms |
コンパイル使用メモリ | 283,608 KB |
実行使用メモリ | 40,476 KB |
最終ジャッジ日時 | 2024-04-30 13:09:49 |
合計ジャッジ時間 | 17,350 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,812 KB |
testcase_01 | AC | 4 ms
6,940 KB |
testcase_02 | AC | 5 ms
6,940 KB |
testcase_03 | AC | 4 ms
6,944 KB |
testcase_04 | AC | 5 ms
6,944 KB |
testcase_05 | AC | 7 ms
6,944 KB |
testcase_06 | AC | 6 ms
6,944 KB |
testcase_07 | AC | 6 ms
6,940 KB |
testcase_08 | AC | 7 ms
6,940 KB |
testcase_09 | AC | 7 ms
6,940 KB |
testcase_10 | AC | 6 ms
6,940 KB |
testcase_11 | AC | 583 ms
31,264 KB |
testcase_12 | AC | 581 ms
31,428 KB |
testcase_13 | AC | 583 ms
31,344 KB |
testcase_14 | AC | 581 ms
31,244 KB |
testcase_15 | AC | 588 ms
31,388 KB |
testcase_16 | AC | 598 ms
34,744 KB |
testcase_17 | AC | 598 ms
34,716 KB |
testcase_18 | AC | 601 ms
34,720 KB |
testcase_19 | AC | 596 ms
34,584 KB |
testcase_20 | AC | 601 ms
34,508 KB |
testcase_21 | AC | 657 ms
32,660 KB |
testcase_22 | AC | 497 ms
30,208 KB |
testcase_23 | AC | 603 ms
40,456 KB |
testcase_24 | AC | 591 ms
40,476 KB |
testcase_25 | AC | 609 ms
40,476 KB |
testcase_26 | AC | 515 ms
24,808 KB |
testcase_27 | AC | 520 ms
24,836 KB |
testcase_28 | AC | 510 ms
24,860 KB |
ソースコード
#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_popcountll template<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=8550 template<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])); } } }