Submission #537395

#	Time	Username	Problem	Language	Result	Execution time	Memory
537395		ac2hu	RMQ (NOI17_rmq)	C++14	100 / 100	56 ms	7992 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];
pair<int,int> fseq[N];
void kill(){
	for(int i= 0;i<n;i++){
		cout << -1 << " ";
	}
	exit(0);
}
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};
		fseq[i] = {-1,-1};
	}
	for(int _ = 0;_<m;_++){
		int l,r,a;cin >> l >> r >> a;
		if(seq[a].first == -1){
			seq[a] = {l,r};
			fseq[a] = {l,r};
		}
		else{
			fseq[a] = {max(fseq[a].first,l), min(fseq[a].second,r)};
			seq[a] = {min(seq[a].first,l), max(seq[a].second, r)};
		}
	}
	set<int> s;
	for(int i = 0;i<n;i++)
		s.insert(i);
	for(int i = n - 1;i>=0;i--){
		if(seq[i].first != -1){
			auto temp = s.lower_bound(fseq[i].first);
			if(temp == s.end() || *temp > fseq[i].second){
				kill();
			}
			else{
				uq[*temp] = i;
				ans[*temp] = i;
				s.erase(temp);
			}
			auto it = s.lower_bound(seq[i].first);
			// --it;
			auto end = s.upper_bound(seq[i].second);
			for(auto tt = it;tt != end;++tt){
				uq[*tt] = i;
			}
			s.erase(it,end);
		}
	}
	// 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){
				kill();
			}
			ans[temp.back()] = i;
			temp.pop_back();
		}
	}
	for(int i =0 ;i<n;i++)
		cout << ans[i] << " ";
	cout << "\n";
}

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