Submission #674942

#	Time	Username	Problem	Language	Result	Execution time	Memory
674942		QwertyPi	RMQ (NOI17_rmq)	C++14	23 / 100	3 ms	2668 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 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 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});
		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();
		if(Q[i].size()) cons2.push_back({l, r, i});
	}
	sort(cons2.begin(), cons2.end(), [](con a, con b){
		return a.l < b.l || a.l == b.l && a.r < b.r;
	});
	
	int l = 0, idx = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	while(l < n){
		while(idx < cons2.size() && cons2[idx].l <= l) pq.push({cons2[idx].r, cons2[idx].m}), idx++;
		if(pq.empty()){
			l++;
		}else{
			auto p = pq.top(); pq.pop();
			if(l > p.fi) die(); used[l] = true, used2[p.se] = true, ans[l++] = p.se;
		}
	}
	while(pq.size()) pq.pop();
	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 lambda function:
rmq.cpp:75:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   75 |   return a.l < b.l || a.l == b.l && a.r < b.r;
      |                       ~~~~~~~~~~~^~~~~~~~~~~~
rmq.cpp: In function 'int main()':
rmq.cpp:81:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<con>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   while(idx < cons2.size() && cons2[idx].l <= l) pq.push({cons2[idx].r, cons2[idx].m}), idx++;
      |         ~~~~^~~~~~~~~~~~~~
rmq.cpp:86:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   86 |    if(l > p.fi) die(); used[l] = true, used2[p.se] = true, ans[l++] = p.se;
      |    ^~
rmq.cpp:86:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   86 |    if(l > p.fi) die(); used[l] = true, used2[p.se] = true, ans[l++] = p.se;
      |                        ^~~~
rmq.cpp:100:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  100 |  for(int i = 0; i < n; i++) cout << ans[i] << ' '; cout << endl;
      |  ^~~
rmq.cpp:100:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  100 |  for(int i = 0; i < n; i++) cout << ans[i] << ' '; cout << endl;
      |                                                    ^~~~

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