제출 #870149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
870149		vjudge1	Deda (COCI17_deda)	C++17	140 / 140	98 ms	8020 KiB

deda

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 25, I = 1e9 + 19;
int n, q, mn[4 * N];

void update(int p, int x, int l, int r, int t) {
	if (r - l == 1) {
		mn[t] = x;
		return;
	}

	int k = (r + l + 1) / 2;
	if (p < k)
		update(p, x, l, k, 2 * t);
	else
		update(p, x, k, r, 2 * t + 1);

	mn[t] = min(mn[2 * t], mn[2 * t + 1]);
}

int find_ans(int p, int x, int l, int r, int t) {
	if (r - l == 1) {
		if (mn[t] > x)
			return -2;
		else
			return l;
	}

	int k = (r + l + 1) / 2;
	if (l < p) {
		int ans = -2;
		if (p < k)
			ans = find_ans(p, x, l, k, 2 * t);

		if (ans == -2)
			return find_ans(p, x, k, r, 2 * t + 1);
		else
			return ans;
	}
	
	if (mn[2 * t] <= x)
		return find_ans(p, x, l, k, 2 * t);
	else
		return find_ans(p, x, k, r, 2 * t + 1);
}

void solve() {
	cin >> n >> q;
	for (int i = 0; i < 4 * N; mn[i++] = I);

	while (q--) {
		char c;
		cin >> c;
		if (c == 'M') {
			int x, a;
			cin >> x >> a;
			update(a - 1, x, 0, n, 1);
		}
		else {
			int y, b;
			cin >> y >> b;
			
			cout << find_ans(b - 1, y, 0, n, 1) + 1 << '\n';
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return cout << '\n', 0;
}

• Subtask 1: 140 / 140