Submission #870152

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870152	2023-11-07T05:25:59 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	117 ms	10840 KB

deda

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

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int N = 2e5 + 12;
int b[N], seg[4 * N], n, q;
pii pl[4 * N];

void pre() {
	cin >> n >> q;
	memset(seg, 127, sizeof seg);
	pl[1] = {0, n};
	for (int i = 1; i < 2 * n; i++) {
		int mid = (pl[i].F + pl[i].S) / 2;
		pl[i * 2] = {pl[i].F, mid};
		pl[i * 2 + 1] = {mid, pl[i].S};
	}
}

void add(int l, int r, int x, int id = 1) {
	if (l <= pl[id].F && r >= pl[id].S) {
		seg[id] = x;
		return;
	}
	if (r <= pl[id].F || l >= pl[id].S) 
		return;
	add(l, r, x, id * 2);
	add(l, r, x, id * 2 + 1);
	seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
}

int ask(int l, int x) {
	int id = 1; 
	vector<int> v;
	while (pl[id].S - pl[id].F > 1) {
		if (pl[id].F == l) {
			v.pb(id);
			break;
		}
		if (l == pl[id].S)
			break;
		id *= 2;
		if (pl[id].S >= l) 
			v.pb(id + 1);
		else
			id++;
	}
	int res = -1;
	for (auto i: v)
		if (seg[i] <= x)
			res = i;
	if (res == -1)
		return -1;
	while (pl[res].S - pl[res].F > 1) 
		res = res * 2 + (seg[res * 2] > x);
	return pl[res].F + 1;
}

void query() {
	while (q--) {
		char tmp;
		cin >> tmp;
		int x, a;
		cin >> x >> a;
		a--;
		if (tmp == 'M') 
			add(a, a + 1, x);
		else
			cout << ask(a, x) << '\n';
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	pre(), query();
	return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	5468 KB	Output is correct
2	Correct	1 ms	5468 KB	Output is correct
3	Correct	3 ms	5468 KB	Output is correct
4	Correct	117 ms	10840 KB	Output is correct
5	Correct	95 ms	10580 KB	Output is correct
6	Correct	103 ms	10580 KB	Output is correct
7	Correct	108 ms	10840 KB	Output is correct