oj.uz

Submission #372941

# Submission time Handle Problem Language Result Execution time Memory
372941 2021-03-02T11:24:44 Z MatinZare Deda (COCI17_deda) C++17
140 / 140
 689 ms 7660 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
int n, m, sg[4 * maxn], ar[maxn], ql, qr, y;
void update(int l, int r, int q, int qval, int id) {
	if (l == q && r == q)
		sg[id] = qval;
	else if (l > q || r < q)
		return;
	else {
		int mid = (l + r) / 2;
		update(l, mid, q, qval, id * 2);
		update(mid + 1, r, q, qval, id * 2 + 1);
		if (sg[id * 2] == 0 && sg[id * 2 + 1] == 0)
			sg[id] = 0;
		else if (sg[id * 2] == 0 || sg[id * 2 + 1] == 0)
			sg[id] = max(sg[id * 2], sg[id * 2 + 1]);
		else
			sg[id] = min(sg[id * 2], sg[id * 2 + 1]);
	}
}
void get(int l, int r, int id) {
	if (l >= ql && r <= qr) {
		//cout << l << ", " << r << " : " << ql << " " << qr << endl;
		if (sg[id] != 0 && sg[id] <= y)
			qr = r;
		if (sg[id] == 0 || sg[id] > y) {
			ql = r + 1;
			return;
		}
	}
	else if (l > qr || r < ql)
		return;
	if (l < r) {
		int mid = (l + r) / 2;
		get(l, mid, id * 2);
		get(mid + 1, r, id * 2 + 1);
	}
}
int main() {
	cin >> n >> m;
	char c;
	while (m--) {
		cin >> c >> qr >> ql;
		if (c == 'M')
			update(1, n, ql, qr, 1), ar[ql] = qr;
		else {
			y = qr, qr = n;
			get(1, n, 1);
			if (ql > qr || ar[qr] > y)
				cout << "-1\n";
			else
				cout << qr << '\n';
		}
	}
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 13 ms 364 KB Output is correct
4 Correct 689 ms 7276 KB Output is correct
5 Correct 537 ms 5996 KB Output is correct
6 Correct 593 ms 7392 KB Output is correct
7 Correct 626 ms 7660 KB Output is correct