結果

問題 No.1675 Strange Minimum Query
ユーザー inksamurai
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0