Submission #870153

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870153	2023-11-07T05:36:21 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	305 ms	4632 KB

deda

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

#define lc id + id
#define rc id + id + 1
#define mid (l + r) / 2
#define X first
#define Y second

const int N = 2e5 + 6;
int n, q, seg[N * 4];
vector<pair<int, pair<int, int>>> P;

void pre() {
	cin >> n >> q;	
	for (int i = 0; i < N * 4; i++)
		seg[i] = INT_MAX;
}

void update(int x, int a, int l = 1, int r = n, int id = 1) {
	if (l > a || a > r)
		return;
	if(l == r) {
		seg[id] = x;
		return;
	}
	update(x, a, l, mid, lc), update(x, a, mid + 1, r, rc);
	seg[id] = min(seg[lc], seg[rc]);
	return;
}

void check(int a, int l = 1, int r = n, int id = 1) {
	if (r < a)
		return;
	if (l >= a) {
		P.push_back({id, {l, r}});
		return;
	}
	check(a, l, mid, lc), check(a, mid + 1, r, rc);
}

int ans(int x, int l, int r, int id) {
	if (l == r)
		return l;
	if (seg[lc] <= x)
		return ans(x, l, mid, lc);
	return ans(x, mid + 1, r, rc);
}

void Q() {
	while(q--) {
		P.clear();
		char c;
		int x, A;
		cin >> c >> x >> A;
		if (c == 'M')
			update(x, A);
		else {
			check(A);
			int k = -1, l = -1, r = -1;;
			for (auto id: P)
				if(seg[id.X] <= x) {
					k = id.X;
					l = id.Y.X, r = id.Y.Y;
					break;
				}
			if (k == -1)
				cout << k << endl;
			else
				cout << ans(x, l, r, k) << endl;

		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	pre();
	Q();
	return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3420 KB	Output is correct
2	Correct	2 ms	3460 KB	Output is correct
3	Correct	7 ms	3420 KB	Output is correct
4	Correct	305 ms	4400 KB	Output is correct
5	Correct	217 ms	4168 KB	Output is correct
6	Correct	243 ms	4632 KB	Output is correct
7	Correct	252 ms	4428 KB	Output is correct