Submission #674953

#	Time	Username	Problem	Language	Result	Execution time	Memory
674953		QwertyPi	RMQ (NOI17_rmq)	C++14	0 / 100	4 ms	5716 KiB

rmq

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

const int MAXN = 1e5 + 11;
struct SegTree{
	int t[MAXN << 2];
	void init() {
		fill(t, t + (MAXN << 2), (1 << 30));
	}
	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, segTree2;

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

vector<con> Q[MAXN];
int ans[MAXN];
bool used[MAXN], used2[MAXN];
int l[MAXN], r[MAXN];

int main(){
	segTree.init(); segTree2.init();
	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});
		Q[m].push_back({l, r, m});
		segTree.upd(l, r, m, 0, 0, n - 1);
	}
	
	auto die = [&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) die();
	}
	
	vector<con> cons2;
	for(int i = 0; i < n; i++){
		int l = 0, r = n - 1;
		for(auto c : Q[i]){
			l = max(l, c.l), r = min(r, c.r);
		}
		if(l > r) die();
	}
	
	for(int i = 0; i < n; i++){
		l[i] = (1 << 30), r[i] = -(1 << 30);
	}
	
	for(int i = 0; i < n; i++){
		int v = segTree.qry(i, i, 0, 0, n - 1);
		if(v == (1 << 30)) continue;
		l[v] = min(l[v], i), r[v] = max(r[v], i);
	}
	
	for(int i = 0; i < n; i++){
		if(l[i] != (1 << 30)){
			cons2.push_back({l[i], r[i], i});
		}
	}
	
	sort(cons2.begin(), cons2.end(), [](con a, con b){
		return a.r - a.l < b.r - b.l;
	});
	
	auto give = [](int idx, int val){
		used[idx] = true, used2[val] = true;
		ans[idx] = val;
	};
	
	for(auto i : cons2){
		for(int j = i.l; j <= i.r; j++){
			if(!used[j]) {
				give(j, i.m);
				break; 
			}
		}
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for(int i = 0; i < n; i++) if(!used[i]) pq.push({segTree.qry(i, i, 0, 0, n - 1), i});
	for(int i = 0; i < n; i++) if(!used2[i]) {
		auto p = pq.top(); pq.pop();
		ans[p.se] = i;
	}
	
	for(int i = 0; i < n; i++) segTree2.upd(i, i, ans[i], 0, 0, n - 1);
	for(int i = 0; i < q; i++){
		int q = segTree2.qry(cons[i].l, cons[i].r, 0, 0, n - 1);
		if(q != cons[i].m) die();
	}
	for(int i = 0; i < n; i++) cout << ans[i] << ' '; cout << endl;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:124:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  124 |  for(int i = 0; i < n; i++) cout << ans[i] << ' '; cout << endl;
      |  ^~~
rmq.cpp:124:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  124 |  for(int i = 0; i < n; i++) cout << ans[i] << ' '; cout << endl;
      |                                                    ^~~~

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