結果
問題 | No.1675 Strange Minimum Query |
ユーザー |
![]() |
提出日時 | 2021-09-10 22:19:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 370 ms / 2,000 ms |
コード長 | 1,007 bytes |
コンパイル時間 | 4,456 ms |
コンパイル使用メモリ | 261,692 KB |
最終ジャッジ日時 | 2025-01-24 11:24:46 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; struct S{ int a; }; struct F{ int a; bool f; }; S op(S a,S b){ return S{min(a.a,b.a)}; } S e(){ return S{1000000000}; } S mapping(F f,S x){ if(f.f){ return S{f.a}; } return x; } F composition(F f,F g){ if(f.f){ return f; } return g; } F id(){ return F{0,false}; } int main(){ int N,Q; cin>>N>>Q; vector<pair<int,pair<int,int>>> A(Q); lazy_segtree<S, op, e, F, mapping, composition, id> seg(N); for(int i=0;i<Q;i++){ cin>>A[i].second.first>>A[i].second.second>>A[i].first; A[i].second.first--; } sort(A.begin(),A.end()); for(int i=0;i<Q;i++){ seg.apply(A[i].second.first,A[i].second.second,F{A[i].first,true}); } for(int i=0;i<Q;i++){ if(seg.prod(A[i].second.first,A[i].second.second).a!=A[i].first){ cout<<"-1\n"; return 0; } } for(int i=0;i<N;i++){ if(i){ cout<<" "; } cout<<seg.get(i).a; } cout<<"\n"; }