Submission #876618

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
876618	2023-11-22T05:45:02 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	80 ms	4568 KB

deda

//ts
#include <bits/stdc++.h>
//The quick brown fox jumps over the lazy dog//
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define ashar(x) setprecision(x)
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define TXT freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
const int maxn = 200010;
const int inf = 2e9;
int n, q;
int seg[4 * maxn];
void upd(int id, int s, int e, int i, int x)
{
	if(i < s or e < i) return;
	if(s == i and e == i)
	{
		seg[id] = x;
		return;
	}
	int mid = (s + e) / 2;
	upd(2 * id, s, mid, i, x);
	upd(2 * id + 1, mid + 1, e, i, x);
	seg[id] = min(seg[2 * id], seg[2 * id + 1]);
}
int get(int id, int s, int e, int l, int r, int stp)
{
	if(r < s or e < l or seg[id] > stp ) return inf;
	if(e == s)
	{
		return s;
	}
	int mid = (s + e) / 2;
	int ans = get(2 * id, s, mid, l, r, stp);
	if(ans != inf)
	{
		return ans;
	}
	return get(2 * id + 1, mid + 1, e, l, r, stp);
}
int main()
{
	fast_io
	cin >> n >> q;
	for(int i = 0; i < 4 * maxn; i++)
	{
		seg[i] = inf;
	}
	while(q--)
	{
		char typ;
		cin >> typ;
		if(typ == 'M')
		{
			int x, a;
			cin >> x >> a;
			upd(1, 1, n, a, x);
			continue;
		}
		int y, b;
		cin >> y >> b;
		int ans = get(1, 1, n, b, n, y);
		if(ans == inf) ans = -1;
		cout << ans << endl;
	}
	return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3416 KB	Output is correct
2	Correct	1 ms	3416 KB	Output is correct
3	Correct	2 ms	3416 KB	Output is correct
4	Correct	80 ms	4568 KB	Output is correct
5	Correct	70 ms	4180 KB	Output is correct
6	Correct	74 ms	4464 KB	Output is correct
7	Correct	74 ms	4388 KB	Output is correct