Submission #426778

#	Time	Username	Problem	Language	Result	Execution time	Memory
426778		nots0fast	RMQ (NOI17_rmq)	C++17	100 / 100	81 ms	14036 KiB

rmq

#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define MAX (int)(pow(10,6) + 10)
#define pb(a) push_back(a)
const ll INF = 0x3f3f3f3f;
const ll inf = pow(10,18);
ll modulo = pow(10,9) + 7;

void badcase(ll n){
	fori(n){
		cout<<-1<<' ';
	}
}

bool srt(vector<ll>& a, vector<ll>& b){
	if(a[1] != b[1]){
		return a[1] < b[1];
	}
	return a[0] < b[0];
}

void deal(){
	ll n, m;
	cin>>n>>m;
	vector<vector<pair<ll, ll> > > all(n);
	fori(m){
		ll li, ri, v;
		cin>>li>>ri>>v;
		all[v].pb(mp(li, ri));
	}
	
	vector<pair<ll,ll> > res(n);
	vector<ll> arr(n, -1);
	
	fori(n){
		res[i] = mp(-1, -1);
		if((ll)all[i].size() == 0){
			continue;
		}
		ll l = -1, r = n+1;
		for(auto& el : all[i]){
			l = max(l, el.ff);
			r = min(r, el.ss);
		}
		if(l > r){
			badcase(n);
			return;
		}
		res[i] = mp(l, r);
	}
	
	set<ll> free;
	fori(n){
		free.insert(i);
	}
	
	vector<vector<ll> > toadd(n);
	
	for(ll i = n-1; i>-1; i--){
		if((ll)free.size() < i+1){
			badcase(n);
			return;
		}
		if(res[i].ff == -1){
			continue;
		}
		{
			ll l = res[i].ff, r = res[i].ss;
			auto it = free.lower_bound(l);
			if(it == free.end() || (*it) > r){
				badcase(n);
				return;
			}
			arr[*it] = i;
			free.erase(it);
		}
		for(auto& el : all[i]){
			ll l = el.ff, r  =el.ss;
			auto it = free.lower_bound(l);
			while(it!=free.end() && (*it) <= r){
				auto itn = it;
				++itn;
				toadd[i].pb(*it);
				free.erase(it);
				it = itn;
			}
		}
	}
	
	fori(n){
		for(auto& el: toadd[i]){
			free.insert(el);
		}
		if(res[i].ff == -1){
			auto it = free.begin();
			arr[*it] = i;
			free.erase(it);
		}
	}
	
	
	
	
	fori(n){
		cout<<arr[i]<<' ';
	}
}


int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}

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