Submission #828824

#	Time	Username	Problem	Language	Result	Execution time	Memory
828824		NK_	RMQ (NOI17_rmq)	C++17	0 / 100	0 ms	212 KiB

rmq

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = double;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
 	
	int N, Q; cin >> N >> Q;

	V<vi> E(N+1); V<array<int, 3>> q;
	vi amt(N);
	for(int i = 0; i < Q; i++) {
		int l, r, x; cin >> l >> r >> x; 
		amt[x]++; q.pb({l, r, x});
		E[l].pb(x);
		E[r+1].pb(~x);
	}

	auto impossible = [&]() {
		for(int i = 0; i < N; i++) cout << -1 << " ";
		cout << nl;
		exit(0-0);
	};

	set<int> have; 
	for(int i = 0; i < N; i++) have.insert(i);

	set<int> S = {-1}, G = {-1}; vi A(N), mn(N);

	vi C(N);
	for(int x = 0; x < N; x++) {
		for(auto& v : E[x]) {
			if (v < 0) {
				v = ~v;
				if (C[v] == amt[v]) G.erase(v);
				C[v]--;	
				if (C[v] == 0) S.erase(S.find(v));
			} else {
				if (C[v] == 0) S.insert(v);
				C[v]++;
				if (C[v] == amt[v]) { G.insert(v); if (have.count(v)) have.erase(v); }
			}
		}

		A[x] = *rbegin(G);
		mn[x] = *rbegin(S);
	}	

	C = vi(N, 0); for(auto x : A) if (x != -1) C[x]++;

	vi ord(N); iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int x, int y) { return mn[x] > mn[y]; });

	for(auto i : ord) {
		int x = A[i];
		if (x != -1 && C[x] == 1) continue;

		auto it = have.lower_bound(mn[i]);
		if (it == end(have)) continue;

		A[i] = *it; have.erase(it);
		if (x != -1) C[x]--;
	}

	if (sz(have) != 0) impossible();
	if (sz(set<int>(begin(A), end(A))) != N) impossible();

	for(auto x : A) cout << x << " ";
	cout << nl;

	exit(0-0);
}					

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