Submission #237069

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
237069	2020-06-04T11:57:20 Z	MrRobot_28	Deda (COCI17_deda)	C++17	140 / 140	139 ms	8056 KB

deda

#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

#	Verdict	Execution time	Memory	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