Submission #372942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
372942	2021-03-02T11:25:52 Z	MatinZare	Deda (COCI17_deda)	C++17	140 / 140	142 ms	4216 KB

deda

#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() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	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	1 ms	364 KB	Output is correct
3	Correct	3 ms	364 KB	Output is correct
4	Correct	131 ms	3820 KB	Output is correct
5	Correct	122 ms	2540 KB	Output is correct
6	Correct	135 ms	3948 KB	Output is correct
7	Correct	142 ms	4216 KB	Output is correct