Submission #697006

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
697006	2023-02-07T21:56:30 Z	BBart888	Deda (COCI17_deda)	C++14	140 / 140	100 ms	7912 KB

deda

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <queue>
#include <fstream>
#include <cmath>
#include<bitset>
#include <array>
#include <stack>
#include<iomanip>
#include <deque>
#include <unordered_map>
#include <random>



using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;


const ll mod1 = 998244353;
const ll mod2 = 1e9+7;
const int MAXN = 2e5 + 111;
const ll S = (1ll << 22) - 1;
const ll pp = 317;
const int ZERO = 1e5;
const int K = 500;




int n, q;
int t[4 * MAXN];


void upd(int v, int tl, int tr, int pos, int val)
{
	if (tl == tr)
	{
		t[v] = val;
	}
	else
	{
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			upd(2 * v, tl, tm, pos, val);
		else
			upd(2 * v + 1, tm + 1, tr, pos, val);
		t[v] = max(t[2 * v], t[2 * v + 1]);
	}
}


int query(int v, int tl, int tr, int l, int r,int val)
{
	//cout << tl << " " << tr << " " << t[v] << " " << val << '\n';
	if (tl > r || tr < l)return -1;
	if (tl >= l && tr <= r)
	{
		if (t[v] < val)
			return -1;
		//cout << tl << " " << tr << " " << val <<" "<<t[v] << endl;
		while (tl != tr)
		{
			int tm = (tl + tr) / 2;
			if (t[2 * v] >= val)
			{
				v = 2 * v;
				tr = tm;
			}
			else
			{
				v = 2 * v + 1;
				tl = tm + 1;
			}
		}
		return tl;
	}

	int tm = (tl + tr) / 2;
	int rs = query(2 * v, tl, tm, l, min(r, tm), val);
	if (rs != -1)return rs;
	return query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
}




int main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	

	cin >> n >> q;

	for (int i = 0; i < 4 * MAXN; i++)
		t[i] = -1e9;

	

	for (int i = 0; i < q; i++)
	{
		char type;
		int x, y;
		cin >> type>>x>>y;
		if (type == 'M')
			upd(1, 0, MAXN, y, -x);
		else
		{
			cout << query(1, 0, MAXN, y, MAXN, -x)<<'\n';
		}

	}


















	return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	4 ms	3412 KB	Output is correct
4	Correct	98 ms	7912 KB	Output is correct
5	Correct	97 ms	7400 KB	Output is correct
6	Correct	93 ms	7716 KB	Output is correct
7	Correct	100 ms	7808 KB	Output is correct