Submission #828821

#	Time	Username	Problem	Language	Result	Execution time	Memory
828821		NK_	RMQ (NOI17_rmq)	C++17	100 / 100	192 ms	20608 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;

struct ST {
	int level(int x) { return 31 - __builtin_clz(x); }
	vi v; V<vi> jmp; int comb(int a, int b) { return min(a, b); }
	void init(const vi& _v) {
		v = _v; jmp = {v};
		for(int j = 1; (1<<j) <= sz(v); j++) {
			jmp.pb(vi(sz(v) - (1<<j) + 1));
			for(int i = 0; i < sz(jmp[j]); i++) jmp[j][i] = comb(jmp[j-1][i], jmp[j-1][i+(1<<(j-1))]);
		}
	}
	int query(int l, int r) {
		int d = level(r-l+1);
		return comb(jmp[d][l], jmp[d][r-(1<<d)+1]);
	}
};

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);

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

	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]--, S.erase(S.find(v));
			} else {
				C[v]++, S.insert(v);
				if (C[v] == amt[v]) { G.insert(v); if (have.count(v)) have.erase(v); }
			}
		}

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

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

	vi CNT(N); for(auto x : A) if (x != -1) CNT[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 && CNT[x] == 1) continue;

		// cout << i << " " << *rbegin(have) << " " << mn[i] << endl;
		auto it = have.lower_bound(mn[i]);
		if (it == end(have)) continue;

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

	ST st; st.init(A);
	for(int j = 0; j < Q; j++) {
		auto [l, r, x] = q[j];
		// cout << st.query(l, r) << " " << x << endl;
		if (st.query(l, r) != x) impossible();
	}

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

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

	exit(0-0);
}					

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