Submission #537367

#	Time	Username	Problem	Language	Result	Execution time	Memory
537367		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];
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;
				}
				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";
	for(int i = 0;i<n;i++){
		if(ans[i] == -1)s.insert(i);
	}
	set<int> s2;
	for(int i = 0;i<n;i++){
		if(seq[i].first == -1){
			deb(s2,i);
			if(s2.size() == 0){
				for(int i= 0;i<n;i++)
					cout << -1 << " ";
				exit(0);
			}
			ans[*s2.begin()] = i;
			s2.erase(s2.begin());
		}
		else{
			auto it = s.lower_bound(seq[i].first);
			auto end = s.upper_bound(seq[i].second);
			// deb(s,*it);
			set<int> temp1 = s;
			for(auto tt = it;tt != end;++tt){
				temp1.erase(temp1.find(*tt));
				s2.insert(*tt);
			}
			swap(temp1,s);
		}
		deb(i,s);
	}
	for(int i =0 ;i<n;i++)
		cout << ans[i] << " ";
}

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