Submission #915249

#	Time	Username	Problem	Language	Result	Execution time	Memory
915249		dsyz	RMQ (NOI17_rmq)	C++17	100 / 100	145 ms	24872 KiB

rmq

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
ll N,Q;
struct node {
	ll s,e,m,lazy;
	pair<ll,ll> v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		lazy = -1;
		v = {-1,s};
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propo() {
		if(lazy == -1) return;
		v.first = max(v.first,lazy);
		if(s != e){
			l->lazy = max(l->lazy,lazy);
			r->lazy = max(r->lazy,lazy);
		}
		lazy = -1;
	}
	void update(ll x,ll y,ll nval){
		propo();
		if(s == x && e == y){
			lazy = max(lazy,nval);
			return;
		}else{
			if(x > m) r -> update(x,y,nval);
			else if(y <= m) l -> update(x,y,nval);
			else l -> update(x,m,nval), r -> update(m + 1,y,nval);
			l->propo(), r->propo();
			v = min(l->v,r->v);
		}
	}
	pair<ll,ll> rmq(ll x,ll y){
		propo();
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r -> rmq(x,y);
			else if(y <= m) return l -> rmq(x,y);
			else return min(l -> rmq(x,m),r -> rmq(m + 1,y));
		}
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>Q;
	root = new node(0,N - 1);
	vector<pair<ll,ll> > ranges[N]; //ranges provided with RMQ = i
	for(ll q = 0;q < Q;q++){
		ll L,R,X;
		cin>>L>>R>>X; //0-indexed
		root -> update(L,R,X);
		ranges[X].push_back({L,R});
	}
	ll ans[N];
	memset(ans,-1,sizeof(ans));
	bool ok = 1;
	set<ll> values;
	for(ll i = 0;i < N;i++){
		values.insert(i);
	}
	for(ll rmq = N - 1;rmq >= 0;rmq--){
		if(ranges[rmq].empty()) continue;
		ll Lb = -1e18, Ub = 1e18;
		for(auto u : ranges[rmq]){
			Lb = max(Lb,u.first);
			Ub = min(Ub,u.second);
		}
		if(Lb > Ub){ //no intersection at all between ranges with RMQ = value rmq
			ok = 0;
			break;
		}
		pair<ll,ll> a = root -> rmq(Lb,Ub);
		if(a.first > rmq){
			ok = 0;
		}else{
			ans[a.second] = rmq; //I can prove that setting any element whose v.first == rmq to value rmq between [Lb,Ub] intersection are always optimal
			values.erase(values.find(rmq));
			root -> update(a.second,a.second,1e9); //position a.second is already filled up
		}
	}
	vector<pair<ll,ll> > left;
	for(ll i = 0;i < N && ok;i++){
		if(ans[i] == -1){
			pair<ll,ll> a = root -> rmq(i,i);
			left.push_back({a.first,i});
		}
	}
	sort(left.begin(),left.end(),greater<pair<ll,ll> >());
	for(auto u : left){
		if(values.empty() || *prev(values.end()) < u.first){
			ok = 0;
			break;
		}else{
			ans[u.second] = *prev(values.end());
			values.erase(prev(values.end()));
		}
	}
	if(!ok){
		memset(ans,-1,sizeof(ans));
		for(ll i = 0;i < N;i++){
			cout<<ans[i]<<" ";
		}
		cout<<'\n';
	}else{
		for(ll i = 0;i < N;i++){
			cout<<ans[i]<<" ";
		}
		cout<<'\n';
	}
}

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