Submission #537373

#	Time	Username	Problem	Language	Result	Execution time	Memory
537373		ac2hu	RMQ (NOI17_rmq)	C++14	0 / 100	0 ms	212 KiB

rmq

#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
const int N = 1e5 + 10;
int n,m;
int ans[N], uq[N];
pair<int,int> seq[N];
signed main() {
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin >> n >> m;
	for(int i =0 ;i<n;i++){
		ans[i] = -1;
		seq[i] = {-1,-1};
	}
	auto merge = [&](pair<int,int> a,pair<int,int> b) -> pair<int,int>{
		return {min(a.first,b.first), max(a.second,b.second)};
		// LARGEST RANGE WHERE IT IS MINIMUM
	};
	for(int _ = 0;_<m;_++){
		int l,r,a;cin >> l >> r >> a;
		if(seq[a].first == -1){
			seq[a] = {l,r};
		}
		else
			seq[a] = merge(seq[a], {l,r});
	}
	for(int i = 0;i<n;i++){
		deb(i,seq[i]);
	}
	set<int> s;
	for(int i = 0;i<n;i++)
		s.insert(i);
	vector<int> not_selected;
	for(int i = n - 1;i>=0;i--){
		if(seq[i].first == -1)
			not_selected.push_back(i);
		else{
			bool sel = false;
			auto it = s.lower_bound(seq[i].first);
			// --it;
			auto end = s.upper_bound(seq[i].second);
			set<int> temp1 = s;
			for(auto tt = it;tt != end;++tt){
				if(!sel){
					sel = true;
					ans[*tt] = i;
				}
				uq[*tt] = max(i, uq[*tt]);
				temp1.erase(temp1.find(*tt));
			}
			if(!sel){
				for(int i= 0;i<n;i++)
					cout << -1 << " ";
				exit(0);
			}
			swap(temp1,s);
		}
	}
	// for(int i =0;i<n;i++)
		// cout << ans[i] << " ";
	// cout << "\n";
	vector<int> temp;
	for(int i =0;i<n;i++){
		if(ans[i] == -1)
			temp.push_back(i);
	}
	sort(temp.begin(),temp.end(),[&](int a,int b){
		return uq[a] < uq[b];
	});
	deb(temp);
	// cout << temp.back() << "\n";
	for(int i = n - 1;i>=0;i--){
		if(seq[i].first == -1){
			if(uq[temp.back()] > i){
				for(int i= 0;i<n;i++)
					cout << -1 << " ";
				exit(0);
			}
			ans[temp.back()] = i;
			temp.pop_back();
		}
	}
	for(int i =0 ;i<n;i++)
		cout << ans[i] << " ";
}

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