제출 #871976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871976		vjudge1	Deda (COCI17_deda)	C++17	80 / 140	236 ms	65536 KiB

deda

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define len(x) (int) x.size()
#define pb push_back
mt19937 rnd(time(0));

struct query {
	char type;
	int a, b;
};

const int N = 2e5 + 7;
unordered_map<int, int> mp;
set<int> seg[N << 2];
vector<query> qu;
vector<int> vec;
int n, q;

void read_input() {
	cin >> n >> q;
	for (int i = 0; i < q; i++) {
		query t;
		cin >> t.type >> t.a >> t.b;
		t.a--;
		vec.pb(t.a);
		qu.pb(t);
	}
}

void prepare() {
	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	for (int i = 0; i < len(vec); i++)
		mp[vec[i]] = i;
}

void upd(int p, int x, int id = 1, int st = 0, int en = len(vec)) {
	if (p < st || p >= en)
		return;
	if (en - st == 1) {
		seg[id].insert(x);
		return;
	}
	int mid = (st + en) >> 1;
	upd(p, x, id << 1, st, mid);
	upd(p, x, id << 1 | 1, mid, en);
	seg[id].insert(x);
}

int get(int l, int r, int b, int id = 1, int st = 0, int en = len(vec)) {
	if (r <= st || l >= en)
		return INT_MAX;
	if (st >= l && en <= r) {
		if (seg[id].empty() || *(--seg[id].end()) < b)
			return INT_MAX;
		return *seg[id].lower_bound(b);
	}
	int mid = (st + en) >> 1;
	return min(get(l, r, b, id << 1, st, mid), get(l, r, b, id << 1 | 1, mid, en));
}

void solve() {
	for (auto q: qu) {
		char type;
		int a, b;
		type = q.type, a = q.a, b = q.b;
		a = mp[a];
		if (type == 'M') {
			upd(a, b);
		}
		else {
			int t = get(0, a + 1, b);
			cout << (t == INT_MAX? -1: t) << '\n';
		}
	}
}

int32_t main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), prepare(), solve();
	return 0;
}

• Subtask 1: 80 / 140