oj.uz

답안 #828824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828824 2023-08-17T16:48:30 Z NK_ RMQ (NOI17_rmq) C++17
0 / 100
 0 ms 212 KB 
// 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.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -