제출 #237213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237213		Mlxa	Deda (COCI17_deda)	C++14	140 / 140	402 ms	5740 KiB

deda

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N   = 1 << 18;
const int INF = 1e18;

int n;
int q;
int t[2 * N];

void upd(int i, int v) {
	t[i += N] = v;
	for (i /= 2; i > 0; i /= 2) {
		t[i] = min(t[i + i], t[i + i + 1]);
	}
}

int query(int l, int r) {
	int mn = INF;
	for (l += N, r += N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1) {
			mn = min(mn, t[l++]);
		}
		if (r % 2 == 0) {
			mn = min(mn, t[r--]);
		}
	}
	return mn;
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	fill_n(t, 2 * N, INF);

	cin >> n >> q;
	while (q--) {
		char tp;
		cin >> tp;
		if (tp == 'M') {
			int x;
			int y;
			cin >> y >> x;
			upd(x, y);
		} else {
			int x;
			int y;
			cin >> y >> x;
			if (query(x, n) > y) {
				cout << "-1\n";
				continue;
			}
			int lef = x - 1, rig = n;
			while (rig - lef > 1) {
				int mid = (lef + rig) / 2;
				if (query(x, mid) <= y) {
					rig = mid;
				} else {
					lef = mid;
				}
			}
			cout << rig << "\n";
		}
	}

	return 0;
}

• Subtask 1: 140 / 140