oj.uz

답안 #237069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237069 2020-06-04T11:57:20 Z MrRobot_28 Deda (COCI17_deda) C++17
140 / 140
 139 ms 8056 KB 
#include<bits/stdc++.h>
using namespace std;
vector <int> tree;
void update(int v, int l, int r, int ind, int val)
{
	if(l == r)
	{
		tree[v] = val;
		return;
	}
	if(ind <= (r + l) / 2)
	{
		update(v * 2, l, (r + l) / 2, ind, val);
	}
	else
	{
		update(v * 2 + 1, (r + l) / 2 + 1, r, ind, val);
	}
	tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
}
int ans(int v, int l, int r, int al, int ar, int y)
{
	if(l >= al && r <= ar)
	{
		if(tree[v] > y)
		{
			return -1;
		}
		if(l == r)
		{
			return l + 1;
		}
		if(tree[v * 2] <= y)
		{
			return ans(v * 2, l, (r + l) / 2, al, ar, y);
		}
		return ans(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, y);
	}
	else if(l <= ar && r >= al)
	{
		int t = ans(v * 2, l, (r + l) / 2, al, ar, y);
		if(t == -1)
		{
			return ans(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, y);
		}
		return t;
	}
	else
	{
		return -1;
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, q;
	cin >> n >> q;
	tree.resize(4 * n, 1e9);
	while(q--)
	{
		char t;
		cin >> t;
		if(t == 'M')
		{
			int x, a;
			cin >> x >> a;
			a--;
			update(1, 0, n - 1, a, x);
		}
		else
		{
			int y, b;
			cin >> y >> b;
			b--;
			cout << ans(1, 0, n - 1, b, n - 1, y) << "\n";
		}
	}
    return 0;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 132 ms 8056 KB Output is correct
5 Correct 117 ms 6008 KB Output is correct
6 Correct 129 ms 7032 KB Output is correct
7 Correct 139 ms 8036 KB Output is correct