oj.uz

답안 #870149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870149 2023-11-07T05:08:52 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 98 ms 8020 KB 
#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.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 3 ms 3552 KB Output is correct
4 Correct 98 ms 8020 KB Output is correct
5 Correct 73 ms 7468 KB Output is correct
6 Correct 80 ms 7728 KB Output is correct
7 Correct 83 ms 8020 KB Output is correct