Submission #1305281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305281		yonatanl	RMQ (NOI17_rmq)	C++20	30 / 100	90 ms	21560 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) {
			return;
		}
		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;
	}
};

struct tr_min {
	ll l, r;
	ll min_val;
	tr_min* lp = nullptr, * rp = nullptr;
	tr_min(ll l, ll r, vll& arr) : l(l), r(r) {
		if (l == r - 1) {
			min_val = arr[l];
			return;
		}
		lp = new tr_min(l, (l + r) / 2, arr);
		rp = new tr_min((l + r) / 2, r, arr);
		pull();
	}
	void pull() {
		min_val = min(lp->min_val, rp->min_val);
	}
	// Query the segment [f,t)
	ll query(ll f, ll t) {
		if (l >= t || r <= f) return INF;
		if (l >= f && r <= t) return min_val;
		return min(lp->query(f, t), rp->query(f, t));
	}
};

void solve() {
	ll n, q;
	cin >> n >> q;
	vector<pair<ll, pll>> queries(q);
	vll maxL(n, -1), minR(n, INF);
	rep(i, 0, q) {
		ll l, r, a;
		cin >> l >> r >> a;
		queries[i] = { a, {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);
	}*/
	sort(queries.begin(), queries.end());
	rep(i, 0, q) {
		seg.update(queries[i].second.first, queries[i].second.second + 1, queries[i].first);
	}
	vll ans(n);
	rep(i, 0, n) {
		ans[i] = seg.query(i);
		if (ans[i] == -1) ans[i] = n - 1;
		//cout << ans[i] << ' ';
	}
	//cout << endl;
	tr_min seg2(0, n, ans);
	rep(i, 0, q) {
		ll l = queries[i].second.first;
		ll r = queries[i].second.second;
		ll a = queries[i].first;
		ll v = seg2.query(l, r + 1);
		if (v != a) {
			rep(j, 0, n) cout << "-1 ";
			cout << endl;
			return;
		}
	}
	rep(i, 0, n) cout << ans[i] << ' ';
	cout << endl;
}

/*
7 8
0 1 2
2 3 2
3 5 1
5 5 3
0 6 1
2 6 1
3 3 6
0 0 3
*/

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

	solve();
}

• Subtask 1: 6.9 / 23
• Subtask 2: 13.2 / 44
• Subtask 3: 9.9 / 33