結果
問題 | 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 secondmt19937_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();}