oj.uz

답안 #82271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
82271 2018-10-29T17:18:12 Z luciocf Deda (COCI17_deda) C++14
140 / 140
 604 ms 3952 KB 
#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.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 12 ms 504 KB Output is correct
4 Correct 604 ms 3952 KB Output is correct
5 Correct 466 ms 3952 KB Output is correct
6 Correct 504 ms 3952 KB Output is correct
7 Correct 552 ms 3952 KB Output is correct