Submission #870149

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870149	2023-11-07T05:08:52 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	98 ms	8020 KB

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.0 / 140.0

#	Verdict	Execution time	Memory	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