結果
問題 | No.1675 Strange Minimum Query |
ユーザー |
![]() |
提出日時 | 2021-09-10 22:41:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 248 ms / 2,000 ms |
コード長 | 1,825 bytes |
コンパイル時間 | 2,006 ms |
コンパイル使用メモリ | 184,260 KB |
実行使用メモリ | 21,952 KB |
最終ジャッジ日時 | 2024-06-12 01:59:42 |
合計ジャッジ時間 | 9,841 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/lazysegtree> #define int long long using namespace std; using namespace atcoder; using vec_int = vector<int>; using vec_ii = vector<vec_int>; using vec_iii = vector<vec_ii>; using vec_iiii = vector<vec_iii>; using P = pair<int,int>; using T = tuple<int,int,int>; using ll = long long; using ld = long double; #define rep(i, n) for(int i = 0; i < (int)(n); i++) void cout_line(vector<int> &a){ for(int i=0;i<a.size();i++){ if(i<a.size()-1){ cout<<a.at(i)<<" "; }else{ cout<<a.at(i)<<endl; } } } int op(int a, int b){ return min(a, b); } int e() { return INT_MAX; } int mapping(int f, int x){ return max(f, x); } int composition(int a, int b){ return max(a, b); } int id(){ return -1; } signed main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, Q; cin>>N>>Q; vec_int l(Q), r(Q), B(Q); rep(i, Q)cin>>l.at(i)>>r.at(i)>>B.at(i); vector<T> Qs(Q); rep(i, Q){ Qs.at(i) = make_tuple(B.at(i), l.at(i), r.at(i)); } sort(Qs.begin(), Qs.end()); reverse(Qs.begin(), Qs.end()); vec_int a(N, -1); lazy_segtree<int, op, e, int, mapping, composition, id> seg(a); rep(i, Q){ int b, L, R; tie(b, L, R) = Qs.at(i); L--; R--; int temp = seg.prod(L, R+1); /* cout<<i<<" "<<L<<" "<<R<<" "<<temp<<endl; for(int j=0;j<5;j++){ cout<<"i="<<i<<" j="<<j<<" "<<seg.get(j)<<endl; } */ if(temp!=-1&&temp>b){ cout<<-1<<endl; return 0; } seg.apply(L, R+1, b); } vec_int ans(N); rep(i,N){ int num = seg.get(i); if(num==-1)num=4545; ans.at(i) = num; } cout_line(ans); return 0; }