Submission #870186

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870186	2023-11-07T07:47:27 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	92 ms	15952 KB

deda

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

#define f first
#define s second
#define mk make_pair

const int N = 1e6 + 7;
int Point[N], Segmin[N], Ans, n, m;
pair<char, pair<int, int>> Ar[N];
pair<int, int> Child[N];
vector <int> node;

void SegmentAns(int u, int w, int ul, int ur) {
	if (ur - ul <= 1) {
		Ans = ul;
		return;
	}
	if (ur - ul <= 1) return;
	int mid = (ur + ul) / 2;
	if (Segmin[u * 2] <= w) SegmentAns(u * 2, w, ul, mid);
	else SegmentAns(u * 2 + 1, w, mid, ur);
}
void Segment(int u, int w, int ul, int ur) {
	if (ul >= w) {
		node.push_back(u);
		return;
	}
	if (ur - ul <= 1 || w > ur - 1) return;
	int mid = (ur + ul) / 2;
	Segment(u * 2, w, ul, mid);
	Segment(u * 2 + 1, w, mid, ur);
}
void solve1(int x, int p) {
	node.clear(), Ans = -1;
	Segment(1, p, 1, (n + 1));
	for (int i = 0; i < node.size(); i++) {
		if (Segmin[node[i]] <= x) {
			SegmentAns(node[i], x, Child[node[i]].f, Child[node[i]].s);
			break;
		}
	}
	cout << Ans << "\n";
}
void update(int u, int w, int w1) {
	if (u < 1) return;
	Segmin[u] = min(Segmin[u], w), update(u / 2, w, w1);
}
void solve() {
	for (int i = 1; i <= m; i++) {
		if (Ar[i].f == 'M') update(Point[Ar[i].s.s], Ar[i].s.f, Ar[i].s.s);
		if (Ar[i].f == 'D') solve1(Ar[i].s.f, Ar[i].s.s);
	}
}
void build(int u, int ul, int ur) {
	Child[u].f = ul, Child[u].s = ur;
	if (ur - ul <= 1) {
		Point[ul] = u;
		return;
	}
	int mid = (ur + ul) / 2;
	build(u * 2, ul, mid);
	build(u * 2 + 1, mid, ur);
}
void input() {
	cin >> n >> m;
	for (int i = 1; i < N; i++)
		Segmin[i] = 1e9 + 7;
	for (int i = 1; i <= m; i++)
		cin >> Ar[i].f >> Ar[i].s.f >> Ar[i].s.s;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input(), build(1, 1, (n + 1)), solve();
}

Compilation message

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

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8540 KB	Output is correct
2	Correct	2 ms	8540 KB	Output is correct
3	Correct	3 ms	8540 KB	Output is correct
4	Correct	92 ms	15880 KB	Output is correct
5	Correct	68 ms	13652 KB	Output is correct
6	Correct	87 ms	15684 KB	Output is correct
7	Correct	79 ms	15952 KB	Output is correct