Submission #674928

#	Time	Username	Problem	Language	Result	Execution time	Memory
674928		QwertyPi	RMQ (NOI17_rmq)	C++14	30 / 100	164 ms	4168 KiB

rmq

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 11;
struct SegTree{
	int t[MAXN << 2];
	void upd(int ql, int qr, int val, int v, int l, int r){
		if(qr < l || r < ql) return;
		if(ql <= l && r <= qr){
			t[v] = max(t[v], val);
			return;
		}
		t[v * 2 + 1] = max(t[v], t[v * 2 + 1]);
		t[v * 2 + 2] = max(t[v], t[v * 2 + 2]);
		int m = (l + r) / 2;
		upd(ql, qr, val, v * 2 + 1, l, m);
		upd(ql, qr, val, v * 2 + 2, m + 1, r);
		t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	int qry(int ql, int qr, int v, int l, int r){
		if(qr < l || r < ql) return (1 << 30);
		if(ql <= l && r <= qr) return t[v];
		t[v * 2 + 1] = max(t[v], t[v * 2 + 1]);
		t[v * 2 + 2] = max(t[v], t[v * 2 + 2]);
		int m = (l + r) / 2;
		return min(qry(ql, qr, v * 2 + 1, l, m), qry(ql, qr, v * 2 + 2, m + 1, r));
	}
} segTree;

struct con{
	int l, r, m;
};

int main(){
	int n, q; cin >> n >> q;
	vector<con> cons;
	for(int i = 0; i < q; i++){
		int l, r, m; cin >> l >> r >> m;
		cons.push_back({l, r, m});
		segTree.upd(l, r, m, 0, 0, n - 1);
	}
	
	auto lose = [&n](){
		for(int i = 0; i < n; i++){
			cout << -1 << ' ';
		}
		cout << endl;
		exit(0);
	};
	
	for(int i = 0; i < q; i++){
		int q = segTree.qry(cons[i].l, cons[i].r, 0, 0, n - 1);
		if(q > cons[i].m) lose();
	}
	
	for(int i = 0; i < n; i++){
		cout << segTree.qry(i, i, 0, 0, n - 1) << ' ';
	}
	cout << endl;
}

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