結果

問題 No.1675 Strange Minimum Query
ユーザー inksamuraiinksamurai
提出日時 2021-09-10 22:24:59
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 135 ms
8,192 KB
testcase_04 AC 151 ms
14,080 KB
testcase_05 AC 19 ms
12,544 KB
testcase_06 AC 160 ms
8,448 KB
testcase_07 AC 198 ms
14,336 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 132 ms
21,120 KB
testcase_11 AC 72 ms
18,816 KB
testcase_12 AC 146 ms
21,888 KB
testcase_13 AC 168 ms
22,464 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 2 ms
5,376 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
権限があれば一括ダウンロードができます

ソースコード

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