Submission #870224

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870224	2023-11-07T09:01:40 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	87 ms	7768 KB

deda

// time :D ?

#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];
vector<pair<int, pair<int, int>>> aa;

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]);
}

void find(int v, int l, int r, int i, int k) {
//	cout << v << " " << l << " " << r << " " << seg[v] << endl;
	if (r < i || aa.size()) {
		return;
	}
	if (l >= i) {
		if (seg[v] <= k) {
			aa.push_back({v, {l, r}});
		}
		return;
	}	

	find(lv, l, mid, i, k);
	if (!aa.size())
		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 {
			aa.clear();
			find(1, 1, n, a, x);
			if (!aa.size()) {
				cout << -1 << endl;
			}

			else {
//				cout << ans.F << " " << ans.S.F << " " << ans.S.S << endl;
				cout << get_ans(aa[0].F, aa[0].S.F, aa[0].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	1 ms	6492 KB	Output is correct
2	Correct	2 ms	6492 KB	Output is correct
3	Correct	3 ms	6488 KB	Output is correct
4	Correct	80 ms	7768 KB	Output is correct
5	Correct	72 ms	7248 KB	Output is correct
6	Correct	77 ms	7504 KB	Output is correct
7	Correct	87 ms	7508 KB	Output is correct