結果
問題 | No.1675 Strange Minimum Query |
ユーザー |
![]() |
提出日時 | 2021-09-10 22:24:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,559 bytes |
コンパイル時間 | 1,968 ms |
コンパイル使用メモリ | 180,664 KB |
実行使用メモリ | 26,624 KB |
最終ジャッジ日時 | 2024-06-12 01:02:44 |
合計ジャッジ時間 | 8,628 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 WA * 22 |
ソースコード
#include <bits/stdc++.h> //eolibraries #define lnf 3999999999999999999 #define inf 999999999+1 #define fi first #define se second #define pb push_back #define all(c) (c).begin(),(c).end() #define sz(c) (int)(c).size() #define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end()); #define rep(i,n) for(int i=0;i<n;i++) #define drep(i,n) for(int i=n-1;i>=0;i--) #define crep(i,x,n) for(int i=x;i<n;i++) #define vec(...) vector<__VA_ARGS__> #define _3E0svGb ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) //eodefine using namespace std; typedef long long ll; typedef long double ld; using pii=pair<int,int>; using tpii=pair<pii,int>; using vi=vec(int); const int mxn=12000; struct lazy_segtree{ int n; vec(ll) seg,lazy,flag; lazy_segtree(int m){ init(m); } void init(int m){ n=1; while(n<m) n*=2; seg.clear(); lazy.clear(); flag.clear(); seg.resize(2*n,lnf); lazy.resize(2*n,0); flag.resize(2*n,false); } void push(int l,int r,int node){ if(flag[node]){ seg[node]=lazy[node]; if(node<n){ // lazy merge lazy[node*2]=lazy[node]; lazy[node*2+1]=lazy[node]; flag[node*2]=flag[node*2+1]=true; } flag[node]=false; lazy[node]=0; } } void set(int node,int l,int r,ll x,int _l,int _r){ push(l,r,node); if(l>=_r or r<=_l) return; if(l>=_l and r<=_r){ lazy[node]=x; flag[node]=true; push(l,r,node); return; } int m=(l+r)>>1; set(node*2,l,m,x,_l,_r); set(node*2+1,m,r,x,_l,_r); // prod seg_node seg[node]=min(seg[node*2],seg[node*2+1]); } ll prod(int node,int l,int r,int _l,int _r){ push(l,r,node); // _e if(l>=_r or r<=_l) return lnf; if(l>=_l and r<=_r) return seg[node]; int m=(l+r)>>1; ll vl=prod(node*2,l,m,_l,_r); ll vr=prod(node*2+1,m,r,_l,_r); return min(vl,vr); } void set(int l,int r,ll x){ // [l,r) set(1,0,n,x,l,r); } ll prod(int l,int r){ // [l,r) return prod(1,0,n,l,r); } }; int main(){ _3E0svGb; int n,m; cin>>n>>m; lazy_segtree seg(n); vec(vec(pii)) qry(n); rep(i,m){ ll l,r,val; cin>>l>>r>>val; l--,r--; qry[r].pb({l,val}); } rep(i,n){ for(auto p : qry[i]){ ll l=p.fi,val=p.se; // if(seg.prod(l,i+1)!=lnf and seg.prod(l,i+1)>val){ // printf("-1\n"); // exit(0); // } seg.set(l,i+1,val); } } rep(i,n){ for(auto p : qry[i]){ int l=p.fi,val=p.se; if(seg.prod(l,i+1)!=val){ printf("-1\n"); exit(0); } } } rep(i,n) if(seg.prod(i,i+1)==lnf) seg.set(i,i+1,inf); rep(i,n){ cout<<seg.prod(i,i+1); if(i<n-1) cout<<" "; } cout<<"\n"; // return 0; }