제출 #1152904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152904		amirrezashoon	Deda (COCI17_deda)	C++17	140 / 140	81 ms	4168 KiB

deda

#include <bits/stdc++.h>
using namespace std;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
const int MAX_N = 2e5 + 7, MAX_M = 321, MAX_V = 1e5 + 7, LOG_N = 19, inf = 2e9 + 7;
const long long INF = 1e18;
int n, q, ind, val, L, R, y, b, a, x, seg[4 * MAX_N], ans[MAX_N];

void build(int l = 0, int r = n, int u = 1) {
	if (r - l == 1) {
		seg[u] = inf;
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, 2 * u);
	build(mid, r, 2 * u + 1);
	seg[u] = inf;
}

void update(int l = 0, int r = n, int u = 1) {
	if (r - l == 1) {
		seg[u] = val;
		return;
	}
	int mid = (l + r) / 2;
	if (ind < mid)
		update(l, mid, 2 * u);
	else
		update(mid, r, 2 * u + 1);
	seg[u] = min(seg[2 * u], seg[2 * u + 1]);
}

void get(int l = 0, int r = n, int u = 1) {
	if (L <= l && r <= R) {
		if (seg[u] <= y)
			R = r;
		else {
			L = r;
			return;
		}
	}
	if (R <= l || r <= L)
		return;
	if (r - l >= 2) {
		int mid = (l + r) / 2;
		get(l, mid, 2 * u);
		get(mid, r, 2 * u + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	build();
	fill(ans, ans + n + 1, inf);
	while (q--) {
		char type;
		cin >> type;
		if (type == 'M') {
			cin >> x >> a;
			a--;
			ind = a, val = x;
			update();
			ans[a] = x;
		}
		else {
			cin >> y >> b;
			L = b - 1, R = n;
			get();
			if (L >= R || ans[L] > y)
				cout << -1 << '\n';
			else
				cout << L + 1 << '\n';
		}
	}
}

• Subtask 1: 140 / 140