제출 #1305259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305259		yonatanl	RMQ (NOI17_rmq)	C++20	0 / 100	0 ms	332 KiB

rmq

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

const ll INF = 1e18;

struct tr {
	ll l, r;
	ll lazy_val = -1;
	tr* lp = nullptr, * rp = nullptr;
	tr(ll l, ll r) : l(l), r(r) {
		if (l == r - 1) {
			lazy_val = -1;
			return;
		}
		push();
		lp = new tr(l, (l + r) / 2);
		rp = new tr((l + r) / 2, r);
	}
	void push() {
		if (lazy_val == -1) return;
		upmax(lp->lazy_val, lazy_val);
		upmax(rp->lazy_val, lazy_val);
		lazy_val = -1;
	}
	// Update the range [f,t) to val
	void update(ll f, ll t, ll val) {
		if (f >= r || t <= l) return;
		if (l >= f && r <= t) {
			lazy_val = val;
			return;
		}
		push();
		lp->update(f, t, val);
		rp->update(f, t, val);
	}
	ll query(ll idx) {
		if (idx >= r || idx < l) return -1;
		if (l == r - 1) {
			return lazy_val;
		}
		push();
		ll v1 = lp->query(idx);
		ll v2 = rp->query(idx);
		if (v1 == -1) return v2;
		return v1;
	}
};

void solve() {
	ll n, q;
	cin >> n >> q;
	vvpll queries(n);
	vll maxL(n, -1), minR(n, INF);
	rep(i, 0, q) {
		ll l, r, a;
		cin >> l >> r >> a;
		queries[a].push_back({ l, r });
		upmax(maxL[a], l);
		upmin(minR[a], r);
	}
	tr seg(0, n);
	rep(i, 0, n) {
		if (maxL[i] > minR[i]) {
			rep(j, 0, n) cout << -1 << ' ';
			cout << endl;
			return;
		}
		//cout << maxL[i] << ' ' << minR[i] << endl;
		if (minR[i] != INF && maxL[i] != -1) seg.update(maxL[i], minR[i] + 1, i);
	}
	vll ans(n);
	set<ll> vals;
	rep(i, 0, n) vals.insert(i);
	rep(i, 0, n) {
		ans[i] = seg.query(i);
		if (ans[i] != -1) vals.erase(ans[i]);
	}
	vector<bool> vis(n, false);
	rep(i, 0, n) {
		//cout << "ans[i] = " << ans[i] << endl;
		if (ans[i] == -1) {
			//ans[i] = *vals.begin();
			//vals.erase(vals.begin());
			ans[i] = n + 1;
		}
		/*else if (vis[ans[i]]) {
			auto it = vals.lower_bound(i);
			if (it == vals.end()) {
				rep(j, 0, n) cout << -1 << ' ';
				cout << endl;
				return;
			}
			ans[i] = *it;
			vals.erase(it);
		}*/
		else if (ans[i] != -1) vis[ans[i]] = true;
	}
	rep(i, 0, n) cout << ans[i] << ' ';
	cout << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	solve();
}

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