Submission #372942

#	Time	Username	Problem	Language	Result	Execution time	Memory
372942		MatinZare	Deda (COCI17_deda)	C++17	140 / 140	142 ms	4216 KiB

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 / 140