Submission #82271

#	Time	Username	Problem	Language	Result	Execution time	Memory
82271		luciocf	Deda (COCI17_deda)	C++14	140 / 140	604 ms	3952 KiB

deda

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;
const int inf = 1e9+10;

int num[maxn], tree[4*maxn];

bool done;

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = inf;
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);
	tree[node] = inf;
}

void upd(int node, int l, int r, int pos, int v)
{
	if (l == r)
	{
		tree[node] = v;
		return;
	}

	int mid = (l+r)>>1;

	if (pos <= mid) upd(2*node, l, mid, pos, v);
	else upd(2*node+1, mid+1, r, pos, v);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

int get(int node, int l, int r, int V)
{
	if (l == r) return l;

	int mid = (l+r)>>1;

	if (tree[2*node] <= V) return get(2*node, l, mid, V);
	return get(2*node+1, mid+1, r, V);
}

int query(int node, int tl, int tr, int l, int r, int V)
{
	if (tl > r || tr < l) return inf;

	if (tl >= l && tr <= r)
	{
		if (done || tree[node] > V) return inf;

		done = 1;
		return get(node, tl, tr, V);
	}

	int mid = (tl+tr)>>1;

	int p1 = query(2*node, tl, mid, l, r, V);
	int p2 = query(2*node+1, mid+1, tr, l, r, V);

	return min(p1, p2);
}

int main(void)
{
	int n, q;
	cin >> n >> q;

	build(1, 1, n);

	while (q--)
	{
		char op;
		cin >> op;

		if (op == 'M')
		{
			int x, a;
			cin >> x >> a;

			upd(1, 1, n, a, x);
		}
		else
		{
			int B, V;
			cin >> V >> B;

			done = 0;

			int ans = query(1, 1, n, B, n, V);

			if (ans == inf) cout << "-1\n";
			else cout << ans << "\n";
		}
	}
}

• Subtask 1: 140 / 140