結果
問題 | No.2421 entersys? |
ユーザー |
|
提出日時 | 2023-08-12 17:27:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 927 ms / 3,000 ms |
コード長 | 5,201 bytes |
コンパイル時間 | 3,418 ms |
コンパイル使用メモリ | 239,552 KB |
最終ジャッジ日時 | 2025-02-16 07:21:13 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;struct LazySegmentTree {private:int n;vector<ll> node, lazy;public:LazySegmentTree(vector<ll> v) {int sz = (int)v.size();n = 1; while(n < sz) n *= 2;node.resize(2*n-1);lazy.resize(2*n-1, 0);for(int i=0; i<sz; i++) node[i+n-1] = v[i];for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];}void eval(int k, int l, int r) {if(lazy[k] != 0) {node[k] += lazy[k];if(r - l > 1) {lazy[2*k+1] += lazy[k] / 2;lazy[2*k+2] += lazy[k] / 2;}lazy[k] = 0;}}void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {if(r < 0) r = n;eval(k, l, r);if(b <= l || r <= a) return;if(a <= l && r <= b) {lazy[k] += (r - l) * x;eval(k, l, r);}else {add(a, b, x, 2*k+1, l, (l+r)/2);add(a, b, x, 2*k+2, (l+r)/2, r);node[k] = node[2*k+1] + node[2*k+2];}}ll getsum(int a, int b, int k=0, int l=0, int r=-1) {if(r < 0) r = n;eval(k, l, r);if(b <= l || r <= a) return 0;if(a <= l && r <= b) return node[k];ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);return vl + vr;}};int main() {int N;cin >> N;vector X(N, ""s);vector L(N, 0), R(N, 0);for(int i = 0; i < N; i++) {cin >> X[i] >> L[i] >> R[i];}int Q;cin >> Q;vector q(Q, 0), t1(0, 0), t2(0, 0), l3(0, 0), r3(0, 0);vector x1(0, ""s), x3(0, ""s);for(int i = 0; i < Q; i++) {cin >> q[i];if(q[i] == 1) {string x;int t;cin >> x >> t;x1.push_back(x);t1.push_back(t);}if(q[i] == 2) {int t;cin >> t;t2.push_back(t);}if(q[i] == 3) {string x;int l, r;cin >> x >> l >> r;x3.push_back(x);l3.push_back(l);r3.push_back(r);}}vector P(0, 0);for(int i = 0; i < N; i++) {P.push_back(L[i]);P.push_back(R[i]);}for(int i = 0; i < t1.size(); i++) {P.push_back(t1[i]);}for(int i = 0; i < t2.size(); i++) {P.push_back(t2[i]);}for(int i = 0; i < l3.size(); i++) {P.push_back(l3[i]);P.push_back(r3[i]);}vector PP(P);sort(begin(PP), end(PP));PP.erase(unique(begin(PP), end(PP)), end(PP));int NN(PP.size());for(int i = 0; i < P.size(); i++) {P[i] = lower_bound(begin(PP), end(PP), P[i]) - begin(PP);}for(int i = 0; i < N; i++) {L[i] = P[i*2];R[i] = P[i*2+1];}for(int i = 0; i < t1.size(); i++) {t1[i] = P[N*2 + i];}for(int i = 0; i < t2.size(); i++) {t2[i] = P[N*2 + t1.size() + i];}for(int i = 0; i < l3.size(); i++) {l3[i] = P[N*2 + t1.size() + t2.size() + i*2];r3[i] = P[N*2 + t1.size() + t2.size() + i*2+1];}vector PX(0, ""s);for(int i = 0; i < N; i++) {PX.push_back(X[i]);}for(int i = 0; i < x1.size(); i++) {PX.push_back(x1[i]);}for(int i = 0; i < x3.size(); i++) {PX.push_back(x3[i]);}vector PPX(PX);sort(begin(PPX), end(PPX));PPX.erase(unique(begin(PPX), end(PPX)), end(PPX));int NNX(PPX.size());vector PXPX(PX.size(), 0);for(int i = 0; i < PXPX.size(); i++) {PXPX[i] = lower_bound(begin(PPX), end(PPX), PX[i]) - begin(PPX);}vector XX(N, 0), xx1(x1.size(), 0), xx3(x3.size(), 0);for(int i = 0; i < N; i++) {XX[i] = PXPX[i];}for(int i = 0; i < xx1.size(); i++) {xx1[i] = PXPX[N + i];}for(int i = 0; i < xx3.size(); i++) {xx3[i] = PXPX[N + xx1.size() + i];}vector<set<int>> S(NNX);vector<map<int, pair<int, int>>> mp(NNX);for(int i = 0; i < N; i++) {S[XX[i]].insert(R[i]);mp[XX[i]][R[i]] = {L[i], R[i]};}LazySegmentTree seg( vector<ll>(NN, 0) );for(int i = 0; i < N; i++) {seg.add(L[i], R[i]+1, 1);}int idx1(0), idx2(0), idx3(0);for(int i = 0; i < Q; i++) {if(q[i] == 1) {string ans("No");auto itr(S[xx1[idx1]].lower_bound(t1[idx1]));if(itr != end(S[xx1[idx1]])) {auto [xxx, yyy] = mp[xx1[idx1]][*itr];if(xxx <= t1[idx1] && t1[idx1] <= yyy) {ans = "Yes";}}cout << ans << endl;idx1++;}if(q[i] == 2) {cout << seg.getsum(t2[idx2], t2[idx2]+1) << endl;idx2++;}if(q[i] == 3) {seg.add(l3[idx3], r3[idx3]+1, 1);S[xx3[idx3]].insert(r3[idx3]);mp[xx3[idx3]][r3[idx3]] = {l3[idx3], r3[idx3]};idx3++;}}return 0;}