結果
問題 |
No.1675 Strange Minimum Query
|
ユーザー |
|
提出日時 | 2021-09-10 22:01:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 387 ms / 2,000 ms |
コード長 | 1,187 bytes |
コンパイル時間 | 1,163 ms |
コンパイル使用メモリ | 86,040 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2024-06-12 00:05:41 |
合計ジャッジ時間 | 12,777 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <atcoder/lazysegtree> #include <algorithm> #include <iostream> using namespace std; using namespace atcoder; typedef pair<int, int> P; typedef pair<int, P> PP; const int INF = 1000000000; struct S { int x; }; S op(S a, S b){ return S{min(a.x, b.x)}; } S e(){ return S{INF}; } struct F { int f; }; S mapping(F f, S a){ if(f.f == 0) return a; return S{f.f}; } F composition(F f, F g){ if(f.f == 0) return g; return f; } F id(){ return F{0}; } int main() { int n, q; cin >> n >> q; PP p[200005]; for(int i = 0; i < q; i++){ int l, r, b; cin >> l >> r >> b; l--; p[i] = PP(b, P(l, r)); } sort(p, p + q); lazy_segtree<S, op, e, F, mapping, composition, id> seg(n); for(int i = 0; i < q; i++){ seg.apply(p[i].second.first, p[i].second.second, F{p[i].first}); } for(int i = 0; i < q; i++){ if(seg.prod(p[i].second.first, p[i].second.second).x != p[i].first){ cout << -1 << endl; return 0; } } for(int i = 0; i < n; i++){ cout << seg.get(i).x; if(i < n - 1) cout << " "; } cout << endl; }