Submission #293171

#	Time	Username	Problem	Language	Result	Execution time	Memory
293171		Berted	RMQ (NOI17_rmq)	C++14	100 / 100	193 ms	9976 KiB

rmq

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define pii pair<int, int>
#define fst first
#define snd second
#define ppi pair<int, pii>
using namespace std;

ppi interval[100001];
vector<int> rollback[100001];
set<int> s;
int n, q, ans[100001];
bool ins[100001];

pii intersect(pii &a, pii &b)
{
	return {max(a.fst, b.fst), min(a.snd, b.snd)};
}

int main()
{
	bool fail = 0;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {ans[i] = -1; s.insert(i);}
	for (int i = 0; i < q; i++)
	{
		cin >> interval[i].snd.fst >> interval[i].snd.snd >> interval[i].fst;
	}
	sort(interval, interval + q, greater<ppi>());

	int j = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		pii ivl = {0, n - 1};
		for (int k = j; k < q && interval[k].fst == i; k++) {ivl = intersect(ivl, interval[k].snd);}
		if (ivl != make_pair(0, n - 1))
		{
			auto it = s.lower_bound(ivl.fst);
			if (it != s.end() && *it <= ivl.snd) {ans[*it] = i; s.erase(it); ins[i] = 1;}
			else {fail = 1; break;}
		}
		for (; j < q && interval[j].fst == i; j++)
		{
			auto it = s.lower_bound(interval[j].snd.fst);
			while (it != s.end() && *it <= interval[j].snd.snd)
			{
				rollback[i].push_back(*it);
				it = s.erase(it);
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (auto &x : rollback[i]) {s.insert(x);}
		if (!ins[i])
		{
			if (s.size()) {ans[*s.begin()] = i; s.erase(s.begin());}
			else {fail = 1; break;}
		} 
	}

	if (fail)
	{
		for (int i = 0; i < n; i++) {ans[i] = -1;}
	}

	for (int i = 0; i < n; i++) 
	{
		cout << ans[i];
		if (i + 1 < n) cout << " ";
	}
	cout << "\n";
	return 0;
}

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