Submission #426734

#	Time	Username	Problem	Language	Result	Execution time	Memory
426734		nots0fast	RMQ (NOI17_rmq)	C++17	0 / 100	1 ms	256 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> > > arr(n);
	fori(m){
		ll li, ri, v;
		cin>>li>>ri>>v;
		arr[v].pb(mp(li, ri));
	}
	
	vector<vector<ll> > que;
	vector<ll> ans(n, -1);
	
	fori(n){
		if((ll)arr[i].size() == 0){
			continue;
		}
		ll l = -1, r = n+1;
		for(auto& el : arr[i]){
			l = max(l, el.ff);
			r = min(r, el.ss);
		}
		if(l > r){
			badcase(n);
			return;
		}
		que.pb(vector<ll>({l, r, i}));
	}
	
	sort(que.begin(), que.end(), srt);
	
	set<ll> free;
	fori(n){
		free.insert(i);
	}
	for(auto& el : que){
		ll li = el[0], ri = el[1];
		auto it = free.lower_bound(li);
		if(it == free.end() || (*it) > ri){
			badcase(n);
			return;
		}
		ans[*it] = el[2];
		free.erase(it);
	}
	
	vector<vector<ll> > toadd(n);
	for(ll i = n-1; i>-1; i--){
		if((ll)arr[i].size() == 0){
			continue;
		}	
		for(auto& el : arr[i]){
			ll li = el.ff, ri = el.ss;
			auto it = free.lower_bound(li);
			while(it!=free.end() && (*it) <= ri){
				auto itn = it;
				++itn;
				toadd[i].pb(*it);
				free.erase(*it);
				it = itn;
			}
		}
	}
	fori(n){
		for(auto& el : toadd[i]){
			free.insert(el);
		}
		if((ll)arr[i].size() != 0){
			continue;
		}
		if((ll)free.size() == 0){
			badcase(n);
			return;
		}
		auto it = free.begin();
		ans[*it] = i; 
		free.erase(it);
	}
	
	fori(n){
		cout<<ans[i]<<' ';
	}
}


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

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