Submission #870234

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870234	2023-11-07T09:27:55 Z	falaz	Deda (COCI17_deda)	C++17	140 / 140	85 ms	7732 KB

deda

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

#define int long long
#define endl '\n'

#define F first 
#define S second

#define lv (v << 1)
#define rv ((v << 1) | 1)
#define mid ((r + l) / 2)


const int N = 2e5 + 25, inf = 1e18;
int n, q, seg[4 * N];

void update(int v, int l, int r, int i, int k) {
	if (l == r) {
		seg[v] = k;
		return;
	}
	(i <= mid) ? update(lv, l , mid, i, k) : update(rv, mid + 1, r, i, k);
	seg[v] = min(seg[lv], seg[rv]);
}

pair<int, pair<int, int>> find(int v, int l, int r, int i, int k) {
//	cout << v << " " << l << " " << r << " " << seg[v] << endl;
	if (r < i) {
		return {inf, {inf, inf}};
	}
	if (l >= i) {
		if (seg[v] <= k) 
			return {v, {l, r}};
		else 
			return {inf, {inf, inf}};
	}
	pair<int, pair<int, int>> a = find(lv, l, mid, i, k);
	if (a.F != inf)
		return a;
	else 
		return find(rv, mid + 1, r, i, k);
	
}

int get_ans(int v, int l, int r, int k) {
	if (l == r)
		return l;
	return ((seg[lv] <= k) ? get_ans(lv, l, mid, k) : get_ans(rv, mid + 1, r, k));
}

void query() {
	cin >> n >> q;
	while (q--) {
		char s;
		int x, a;
		cin >> s >> x >> a;
		if (s == 'M') 
			update(1, 1, n, a, x);
		else {
			pair<int, pair<int, int>> ans = find(1, 1, n, a, x);
			if (ans.F == inf) {
				cout << -1 << endl;
			}
			else {
//				cout << ans.F << " " << ans.S.F << " " << ans.S.S << endl;
				cout << get_ans(ans.F, ans.S.F, ans.S.S, x) << endl;
			}
		}
	
	}
}

void run() {
	memset(seg, 127, sizeof(seg));
	query();
}

signed main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	run();
}	

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	2 ms	6492 KB	Output is correct
3	Correct	3 ms	6492 KB	Output is correct
4	Correct	84 ms	7732 KB	Output is correct
5	Correct	85 ms	7392 KB	Output is correct
6	Correct	78 ms	7440 KB	Output is correct
7	Correct	85 ms	7576 KB	Output is correct