Submission #876618

#	Time	Username	Problem	Language	Result	Execution time	Memory
876618		vjudge1	Deda (COCI17_deda)	C++17	140 / 140	80 ms	4568 KiB

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 / 140