結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー |
|
提出日時 | 2024-02-23 21:55:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 290 ms / 2,500 ms |
コード長 | 3,002 bytes |
コンパイル時間 | 2,157 ms |
コンパイル使用メモリ | 187,564 KB |
実行使用メモリ | 21,108 KB |
最終ジャッジ日時 | 2024-09-29 06:25:31 |
合計ジャッジ時間 | 10,306 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#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(); }