結果
問題 |
No.2650 [Cherry 6th Tune *] セイジャク
|
ユーザー |
|
提出日時 | 2024-02-24 01:54:59 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 266 ms / 2,500 ms |
コード長 | 1,277 bytes |
コンパイル時間 | 26,002 ms |
コンパイル使用メモリ | 358,396 KB |
最終ジャッジ日時 | 2025-02-19 20:55:05 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using P=pair<ll,ll>; void IO(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); } using S = long long; using F = long long; const S INF = 8e18; const F ID = 8e18; S op(S a, S b){ return std::max(a, b); } S e(){ return -INF; } S mapping(F f, S x){ return (f == ID ? x : f); } F composition(F f, F g){ return (f == ID ? g : f); } F id(){ return ID; } int main(){ IO(); ll n,a; cin>>n>>a; vector<P> info(n); for(ll i=0;i<n;i++){ cin>>info[i].first; info[i].second=i; } sort(info.begin(),info.end()); vector<ll> x(n); for(ll i=0;i<n;i++){ x[i]=info[i].first; } lazy_segtree<S,op,e,F,mapping,composition,id> seg(n); ll t; cin>>t; for(ll i=1;i<=t;i++){ ll l,r; cin>>l>>r; ll vl=lower_bound(x.begin(),x.end(),l)-x.begin(); ll vr=upper_bound(x.begin(),x.end(),r)-x.begin(); seg.apply(vl,vr,i); } vector<ll> ans(n); for(ll i=0;i<n;i++){ if(seg.get(i)==-INF){ ans[info[i].second]=-1; }else{ ans[info[i].second]=seg.get(i); } } for(ll i=0;i<n;i++){ cout<<ans[i]<<endl; } }