oj.uz

답안 #674956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
674956 2022-12-26T17:05:27 Z QwertyPi RMQ (NOI17_rmq) C++14
23 / 100
 4 ms 5844 KB 
#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);
	}
	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 ll[MAXN], rr[MAXN];
int main(){
	segTree.init(); segTree2.init();
	int n, q; cin >> n >> q;
	fill(ans, ans + n, -1);
	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();
		ll[i] = l, rr[i] = r;
	}
	
	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) 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)){
			l[i] = max(l[i], ll[i]); r[i] = min(r[i], rr[i]);
			if(l[i] > r[i]) die();
			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

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

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 4 ms 5776 KB Output is correct
5 Correct 3 ms 5796 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 3 ms 5792 KB Output is correct
10 Correct 3 ms 5716 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct

Subtask #2
0.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 4 ms 5776 KB Output is correct
5 Correct 3 ms 5796 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 3 ms 5792 KB Output is correct
10 Correct 3 ms 5716 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Incorrect 4 ms 5844 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 4 ms 5776 KB Output is correct
5 Correct 3 ms 5796 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 3 ms 5792 KB Output is correct
10 Correct 3 ms 5716 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Incorrect 4 ms 5844 KB Output isn't correct
13 Halted 0 ms 0 KB -