結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー | umimel |
提出日時 | 2024-02-23 21:55:10 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 306 ms / 2,500 ms |
コード長 | 3,002 bytes |
コンパイル時間 | 2,103 ms |
コンパイル使用メモリ | 187,240 KB |
実行使用メモリ | 21,040 KB |
最終ジャッジ日時 | 2024-02-23 21:55:44 |
合計ジャッジ時間 | 10,172 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge16 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 54 ms
7,936 KB |
testcase_03 | AC | 37 ms
6,676 KB |
testcase_04 | AC | 203 ms
12,608 KB |
testcase_05 | AC | 160 ms
12,328 KB |
testcase_06 | AC | 71 ms
7,976 KB |
testcase_07 | AC | 167 ms
12,464 KB |
testcase_08 | AC | 49 ms
6,676 KB |
testcase_09 | AC | 278 ms
21,040 KB |
testcase_10 | AC | 280 ms
21,040 KB |
testcase_11 | AC | 306 ms
21,040 KB |
testcase_12 | AC | 304 ms
21,040 KB |
testcase_13 | AC | 276 ms
21,040 KB |
testcase_14 | AC | 280 ms
21,040 KB |
testcase_15 | AC | 300 ms
21,040 KB |
testcase_16 | AC | 196 ms
21,040 KB |
testcase_17 | AC | 197 ms
21,040 KB |
testcase_18 | AC | 197 ms
21,040 KB |
testcase_19 | AC | 196 ms
21,040 KB |
testcase_20 | AC | 221 ms
21,040 KB |
testcase_21 | AC | 203 ms
21,040 KB |
testcase_22 | AC | 201 ms
21,040 KB |
testcase_23 | AC | 175 ms
21,040 KB |
testcase_24 | AC | 169 ms
21,040 KB |
testcase_25 | AC | 178 ms
21,040 KB |
testcase_26 | AC | 169 ms
21,040 KB |
testcase_27 | AC | 171 ms
21,040 KB |
testcase_28 | AC | 168 ms
21,040 KB |
testcase_29 | AC | 175 ms
21,040 KB |
testcase_30 | AC | 177 ms
21,040 KB |
testcase_31 | AC | 236 ms
21,040 KB |
testcase_32 | AC | 87 ms
8,168 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i) #define rep(i, n) drep(i, 0, n - 1) #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); const ll MOD1000000007 = 1000000007; const ll MOD998244353 = 998244353; const ll MOD[3] = {999727999, 1070777777, 1000000007}; const ll LINF = 1LL << 60LL; const int IINF = (1 << 30) - 1; struct LazySegmentTree{ ll n; vector<ll> data, lazy; vector<bool> lazyFlag; LazySegmentTree(ll n_){ n = 1; while (n < n_) n *= 2; data.resize(2*n, LINF); lazy.resize(2*n, LINF); lazyFlag.resize(2*n, false); } void eval(ll k, ll l, ll r){ if(lazyFlag[k]){ data[k] = lazy[k]; if(r-l > 1){ lazy[2*k+1] = lazy[2*k+2] = lazy[k]; lazyFlag[2*k+1] = lazyFlag[2*k+2] = true; } lazyFlag[k] = false; } } void update(ll a, ll b, ll x){update_sub(a, b, x, 0, 0, n);} void update_sub(ll a, ll b, ll x, ll k, ll l, ll r){ eval(k, l, r); if(a <= l && r <= b){ lazy[k] = x; lazyFlag[k] = true; eval(k, l, r); }else if(!(b <= l || r <= a)){ update_sub(a, b, x, 2*k+1, l, (l+r)/2); update_sub(a, b, x, 2*k+2, (l+r)/2, r); data[k] = min(data[2*k+1], data[2*k+2]); } } // the minimun element of [a, b) ll query(ll a, ll b){return query_sub(a, b, 0, 0, n);} ll query_sub(ll a, ll b, ll k, ll l, ll r){ if(r <= a || b <= l){ return LINF; }else if(a <= l && r <= b){ eval(k, l, r); return data[k]; }else{ eval(k, l, r); ll vl = query_sub(a, b, 2*k+1, l, (l+r)/2); ll vr = query_sub(a, b, 2*k+2, (l+r)/2, r); return min(vl, vr); } } }; void solve(){ int N, A; cin >> N >> A; vector<int> X(N); for(int i=0; i<N; i++) cin >> X[i]; int T; cin >> T; vector<int> L(T), R(T); for(int i=0; i<T; i++) cin >> L[i] >> R[i]; int M; { vector<int> cmp; for(int i=0; i<N; i++) cmp.pb(X[i]); for(int i=0; i<T; i++){ cmp.pb(L[i]); cmp.pb(R[i]); } sort(all(cmp)); cmp.erase(unique(all(cmp)), cmp.end()); for(int i=0; i<N; i++) X[i] = lower_bound(all(cmp), X[i])-cmp.begin(); for(int i=0; i<T; i++){ L[i] = lower_bound(all(cmp), L[i])-cmp.begin(); R[i] = lower_bound(all(cmp), R[i])-cmp.begin(); } M = (int)cmp.size(); } LazySegmentTree seg(M); for(int i=0; i<T; i++){ seg.update(L[i], R[i]+1, i+1); } for(int i=0; i<N; i++){ ll ans = seg.query(X[i], X[i]+1); if(ans==LINF) cout << -1 << '\n'; else cout << ans << '\n'; } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int T=1; // cin >> T; while(T--) solve(); }