結果

問題 No.1676 Coin Trade (Single)
ユーザー inksamuraiinksamurai
提出日時 2021-09-10 22:24:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,559 bytes
コンパイル時間 2,318 ms
コンパイル使用メモリ 180,676 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-06-12 01:01:53
合計ジャッジ時間 7,154 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
権限があれば一括ダウンロードができます

ソースコード

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