結果
問題 | No.2220 Range Insert & Point Mex |
ユーザー | karinohito |
提出日時 | 2023-02-17 22:23:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 812 ms / 2,000 ms |
コード長 | 6,318 bytes |
コンパイル時間 | 6,169 ms |
コンパイル使用メモリ | 285,432 KB |
実行使用メモリ | 73,112 KB |
最終ジャッジ日時 | 2023-09-28 18:07:32 |
合計ジャッジ時間 | 21,233 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,384 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 1 ms
4,376 KB |
testcase_13 | AC | 696 ms
63,928 KB |
testcase_14 | AC | 708 ms
63,864 KB |
testcase_15 | AC | 711 ms
63,948 KB |
testcase_16 | AC | 711 ms
63,820 KB |
testcase_17 | AC | 696 ms
63,868 KB |
testcase_18 | AC | 697 ms
63,744 KB |
testcase_19 | AC | 695 ms
63,836 KB |
testcase_20 | AC | 801 ms
73,112 KB |
testcase_21 | AC | 812 ms
72,992 KB |
testcase_22 | AC | 792 ms
72,996 KB |
testcase_23 | AC | 456 ms
29,920 KB |
testcase_24 | AC | 368 ms
29,244 KB |
testcase_25 | AC | 350 ms
24,160 KB |
testcase_26 | AC | 391 ms
29,700 KB |
testcase_27 | AC | 129 ms
14,504 KB |
testcase_28 | AC | 228 ms
18,620 KB |
testcase_29 | AC | 233 ms
18,620 KB |
testcase_30 | AC | 233 ms
18,676 KB |
testcase_31 | AC | 364 ms
28,172 KB |
testcase_32 | AC | 309 ms
24,864 KB |
testcase_33 | AC | 342 ms
24,932 KB |
testcase_34 | AC | 563 ms
43,456 KB |
testcase_35 | AC | 613 ms
43,140 KB |
testcase_36 | AC | 439 ms
31,472 KB |
testcase_37 | AC | 491 ms
31,240 KB |
testcase_38 | AC | 515 ms
43,360 KB |
ソースコード
#include <bits/stdc++.h> #include <cassert> #include <cmath> #include <complex> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; #define all(A) A.begin(),A.end() #define rep(i, n) for (ll i = 0; i < (ll) (n); i++) template<class T> bool chmax(T& p, T q, bool C = 1) { if (C == 0 && p == q) { return 1; } if (p < q) { p = q; return 1; } else { return 0; } } template<class T> bool chmin(T& p, T q, bool C = 1) { if (C == 0 && p == q) { return 1; } if (p > q) { p = q; return 1; } else { return 0; } } ll gcd(ll(a), ll(b)) { if (a == 0)return b; if (b == 0)return a; ll c = a; while (a % b != 0) { c = a % b; a = b; b = c; } return b; } ll sqrtz(ll N) { ll L = 0; ll R = sqrt(N) + 10000; while (abs(R - L) > 1) { ll mid = (R + L) / 2; if (mid * mid <= N)L = mid; else R = mid; } return L; } using mint = modint998244353; /* 区間をsetで管理するテク 区間は半開区間で持たせる[L,R) */ ll cnt=0; vll AN; ll cm = 0; template<class T> struct rangeset { set<pair<T, T>> S; T INF; rangeset() { INF = 2e18;; S.insert({ INF,INF }); S.insert({ -INF,-INF }); } bool iscovered(T L, T R) { //assert(L<=R); auto itr = S.lower_bound({ L + 1,L + 1 }); itr = prev(itr); auto st = *itr; return (itr->first <= L && R <= itr->second); } bool iscovered(T x) { return iscovered(x, x + 1); } pair<T, T> covered(T L, T R) { //assert(L<=R); auto itr = S.lower_bound({ L + 1,L + 1 }); itr--; auto st = *itr; if (itr->first <= L && R <= itr->second) { return st; } else { return { INF,INF }; } } pair<T, T> covered(T x) { return covered(x, x + 1); } T insert(T L, T R) { if (iscovered(L, R))return T(0); auto itr = S.lower_bound({ L + 1,L + 1 }); itr = prev(itr); T res = T(0); auto st = *itr; if (itr->first <= L && L <= itr->second) { L = st.first; res -= itr->second - itr->first; itr = S.erase(itr); } else itr = next(itr); while (R > itr->second) { res -= itr->second - itr->first; itr = S.erase(itr); } if (itr->first <= R && R <= itr->second) { res -= itr->second - itr->first; R = itr->second; itr = S.erase(itr); } S.insert({ L,R }); res += R - L; return res; } T insert(T x) { return insert(x, x + 1); } T erase(T L, T R) { auto itr = S.lower_bound({ L + 1,L + 1 }); itr = prev(itr); T res = T(0); auto st = *itr; if (itr->first <= L && R <= itr->second) { if (itr->first < L)S.insert({ itr->first,L }); if (R < itr->second)S.insert({ R,itr->second }); for (ll p = L; p < R; p++) { AN[p] = cm; cnt++; } S.erase(itr); return R - L; } if (itr->first <= L && L < itr->second) { res += itr->second - L; if (itr->first < L)S.insert({ itr->first,L }); for (ll p = L; p < itr->second; p++) { AN[p] = cm; cnt++; } itr = S.erase(itr); } else itr = next(itr); while (itr->second <= R) { res += itr->second - itr->first; for (ll p = itr->first; p < itr->second; p++) { AN[p] = cm; cnt++; } itr = S.erase(itr); } if (itr->first < R && R <= itr->second) { res += R - itr->first; if (R < itr->second)S.insert({ R,itr->second }); for (ll p = itr->first; p < R; p++) { AN[p] = cm; cnt++; } S.erase(itr); } return res; } T erase(T x) { return erase(x, x + 1); } }; struct S { ll a; int size; }; struct F { ll a, b; }; S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; } S e() { return S{0, 0}; } S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; } F composition(F l, F r) { return F{r.a * l.a, r.b * l.a + l.b}; } F id() { return F{1, 0}; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); //rangeset<ll> S; map<ll, vector<pair<ll, ll>>> P; ll N; cin >> N; map<ll, ll> M; rep(i, N) { ll L, R, A; cin >> L >> R >> A; M[L] = M[R] = 1; P[A].push_back({ L,R }); } ll Q; cin >> Q; vll X(Q); rep(i, Q) { ll x; cin >> x; M[x] = 1; X[i] = x; } ll m = 0; for (auto mm : M) { M[mm.first] = m; m++; } rep(i,N){ vector<pair<ll,ll>> NP; sort(all(P[i])); ll NL=-1; ll NR=-1; for(auto lr:P[i]){ ll L=lr.first; ll R=lr.second; if(NR+1<L){ if(NR!=-1)NP.push_back({NL,NR}); NL=L; NR=R; } else{ NR=max(NR,R); } } if(NR!=-1){ NP.push_back({NL,NR}); } P[i]=NP; for(auto lr: NP){ //cout<<i<<" "<<lr.first<<" "<<lr.second<<endl; } } AN.assign(m, N); lazy_segtree<S, op, e, F, mapping, composition, id> seg(m); rep(i,m){ seg.set(i,S{N,1}); } for(ll i=N-1;i>=0;i--) { ll LL = 0; cm = i; for (auto lr : P[i]) { ll L = M[lr.first]; ll R = M[lr.second]; seg.apply(LL,L,F{0,i}); //if (LL < L)S.erase(LL, L); LL = R + 1; } seg.apply(LL,m,F{0,i}); //S.erase(LL, m + 1); } rep(q, Q) { cout << seg.get(M[X[q]]).a << endl; } //cout<<cnt<<endl; }