Submission #294530

#	Time	Username	Problem	Language	Result	Execution time	Memory
294530		nandonathaniel	RMQ (NOI17_rmq)	C++14	100 / 100	218 ms	9068 KiB

rmq

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
const int MAXN=100005;
int a[MAXN],n,lazy[4*MAXN];
bool udah[MAXN],udhidx[MAXN];
pii segment[MAXN],tree[4*MAXN];

void updatenode(int now,int val){
	tree[now].first+=val;
	lazy[now]+=val;
}

void ganti1(int pos,int val){
	tree[pos].first=max(tree[pos].first,val);
}
 
void build(int now,int L,int R){
	if(L==R){
		tree[now]={a[L],L};
		return;
	}
	int mid=(L+R)/2;
	build(2*now,L,mid);
	build(2*now+1,mid+1,R);
	tree[now]=min(tree[2*now],tree[2*now+1]);
}
 
void pushdown(int now){
	updatenode(2*now,lazy[now]);
	updatenode(2*now+1,lazy[now]);
	lazy[now]=0;
	ganti1(2*now,tree[now].first);
	ganti1(2*now+1,tree[now].first);
}
 
void update(int now,int L,int R,int x,int y,int val){
	if(L>=x && R<=y){
		ganti1(now,val);
		return;
	}
	if(L>y || R<x)return;
	pushdown(now);
	int mid=(L+R)/2;
	update(2*now,L,mid,x,y,val);
	update(2*now+1,mid+1,R,x,y,val);
	tree[now]=min(tree[2*now],tree[2*now+1]);
}

pii query(int now,int L,int R,int x,int y){
	if(L>=x && R<=y)return tree[now];
	if(L>y || R<x)return {1e9,1e9};
	pushdown(now);
	int mid=(L+R)/2;
	return min(query(2*now,L,mid,x,y),query(2*now+1,mid+1,R,x,y));
}

void gagal(){
	for(int i=1;i<=n;i++){
		cout << -1;
		if(i<n)cout << " ";
		else cout << '\n';
	}
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int q,u,v,w;
	cin >> n >> q;
	vector<piii> que;
	for(int i=1;i<=q;i++){
		cin >> u >> v >> w;
		u++;v++;w++;
		que.push_back({w,{u,v}});
	}
	for(int i=1;i<=n;i++){
		a[i]=-1;
		segment[i].first=-1;
		segment[i].second=-1;
	}
	build(1,1,n);
	sort(que.begin(),que.end());
	reverse(que.begin(),que.end());
	for(auto isi : que){
		//for(int i=1;i<=n;i++)cout << query(1,1,n,i,i).first << " ";
		//cout << '\n';
		if(segment[isi.first].first==-1){
			segment[isi.first].first=isi.second.first;
			segment[isi.first].second=isi.second.second;
		}
		else{
			if(segment[isi.first].second<isi.second.first){
				gagal();
			}
			else if(isi.second.second<segment[isi.first].first){
				gagal();
			}
			segment[isi.first].first=max(segment[isi.first].first,isi.second.first);
			segment[isi.first].second=min(segment[isi.first].second,isi.second.second);
		}
		int x=isi.second.first,y=isi.second.second;
		pii tanya=query(1,1,n,isi.second.first,isi.second.second);
		if(tanya.first==-1 || tanya.first==isi.first){
			update(1,1,n,isi.second.first,isi.second.second,isi.first);
		}
		else{
			gagal();
		}
	}
	vector<pii> V;
	for(int i=1;i<=n;i++){
		if(segment[i].first==-1)continue;
		pii tanya=query(1,1,n,segment[i].first,segment[i].second);
		if(tanya.first==i){
			udah[i]=true;
			udhidx[tanya.second]=true;
		}
		else gagal();
	}
	for(int i=1;i<=n;i++)a[i]=query(1,1,n,i,i).first;
	for(int i=1;i<=n;i++){
		if(udhidx[i])continue;
		V.push_back({a[i],i});
	}
	sort(V.begin(),V.end());
	reverse(V.begin(),V.end());
	int now=n;
	for(auto isi : V){
		while(now>=1 && udah[now])now--;
		if(now==0)gagal();
		if(isi.first>now)gagal();
		a[isi.second]=now;
		udah[now]=true;
	}
	for(int i=1;i<=n;i++){
		cout << a[i]-1;
		if(i<n)cout << " ";
		else cout << '\n';
	}
	return 0;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:103:7: warning: unused variable 'x' [-Wunused-variable]
  103 |   int x=isi.second.first,y=isi.second.second;
      |       ^
rmq.cpp:103:26: warning: unused variable 'y' [-Wunused-variable]
  103 |   int x=isi.second.first,y=isi.second.second;
      |                          ^

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33