Submission #870527

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870527	2023-11-08T08:01:23 Z	Amirmohammad_sh	Deda (COCI17_deda)	C++17	140 / 140	106 ms	15444 KB

deda

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

struct query {
	char c;
	int x, y;
};

const int N = 2e5 + 10;
query q[N];
vector<int> node;
pair<int, int> child[N];
int n, m, cnt = 1, id[N], id1[4 * N], sg[4 * N];

void build(int v, int l, int r) {
	if (l == r) {
		id[l] = v;
		id1[v] = l;
		return;
	}
	int mid = (l + r) / 2;
	build(2 * v, l, mid);
	build(2 * v + 1, mid + 1, r);
}

void update(int i, int x) {
	int v = id[i];
	sg[v] = x;
	v /= 2;
	while (v != 0) {
		sg[v] = min(sg[2 * v], sg[2 * v + 1]);
		v /= 2;
	}
}

void get(int v, int i, int j, int l, int r) {
	if (i > r || j < l) {
		return;
	}
	if (i >= l && j <= r) {
		node.push_back(v);
		return;
	}
	int mid = (i + j) / 2;
	get(2 * v, i, mid, l, r);
	get(2 * v + 1, mid + 1, j, l, r);
}

void add(int a, int x) {
	int i = lower_bound(child + 1, child + cnt, make_pair(a, x)) - child;
	update(i, x);
}

int find_ans(int v, int y) {
	if (id1[v] != 0) {
		return id1[v];
	}
	if (sg[2 * v] <= y) {
		return find_ans(2 * v, y);
	}
	else {
		return find_ans(2 * v + 1, y);
	}
}

void find(int b, int y) {
	int l = 0, r = cnt;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		if (child[mid].first >= b) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	node.clear();
	get(1, 1, cnt - 1, r, cnt - 1);
	bool flag = false;
	for (int i = 0; i < node.size(); i++) {
		if (sg[node[i]] <= y) {
			flag = true;
			int k = find_ans(node[i], y);
			cout << child[k].first << "\n";
			break;
		}
	}
	if (!flag) {
		cout << -1 << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> q[i].c >> q[i].x >> q[i].y;
		if (q[i].c == 'M') {
			child[cnt] = {q[i].y, q[i].x};
			cnt++;
		}
	}
	sort(child + 1, child + cnt);
	memset(sg, 63, sizeof sg);
	build(1, 1, cnt - 1);
	for (int i = 0; i < m; i++) {
		char c = q[i].c;
		int x = q[i].x, y = q[i].y;
		if (c == 'M') {
			add(y, x);
		}
		else {
			find(y, x);
		}
	}
}

Compilation message

deda.cpp: In function 'void find(int, int)':
deda.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i < node.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	10844 KB	Output is correct
2	Correct	1 ms	10844 KB	Output is correct
3	Correct	3 ms	10844 KB	Output is correct
4	Correct	69 ms	15444 KB	Output is correct
5	Correct	99 ms	14928 KB	Output is correct
6	Correct	106 ms	15220 KB	Output is correct
7	Correct	100 ms	15376 KB	Output is correct