oj.uz

Submission #674926

# Submission time Handle Problem Language Result Execution time Memory
674926 2022-12-26T15:36:24 Z QwertyPi RMQ (NOI17_rmq) C++14
0 / 100
 0 ms 212 KB 
#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(l <= ql && qr <= r){
			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] = max(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(l <= ql && qr <= r) 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 max(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
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -