oj.uz

답안 #870204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870204 2023-11-07T08:44:21 Z vjudge1 Deda (COCI17_deda) C++17
0 / 140
 82 ms 7732 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

#define F first 
#define S second

#define lv (v << 1)
#define rv ((v << 1) | 1)
#define mid ((r + l) / 2)


const int N = 2e5 + 25, inf = 1e18;
int n, q, seg[4 * N];

void update(int v, int l, int r, int i, int k) {
	if (l == r) {
		seg[v] = k;
		return;
	}
	(i <= mid) ? update(lv, l , mid, i, k) : update(rv, mid + 1, r, i, k);
	seg[v] = min(seg[lv], seg[rv]);
}

pair<int, pair<int, int>> find(int v, int l, int r, int i, int k) {
//	cout << v << " " << l << " " << r << " " << seg[v] << endl;
	if (r < i) {
		return {inf, {inf, inf}};
	}
	if (l >= i) {
		if (seg[v] <= k) 
			return {v, {l, r}};
		else 
			return {inf, {inf, inf}};
	}
	pair<int, pair<int, int>> a = find(lv, l, mid, i, k);
	if (a.F != inf)
		return a;
	else 
		return find(rv, mid + 1, r, i, k);
	
}

int get_ans(int v, int l, int r, int k) {
	if (l == r)
		return l;
	return ((seg[lv] <= k) ? get_ans(lv, l, mid, k) : get_ans(rv, mid + 1, r, k));
}

void query() {
	cin >> n >> q;
	while (q--) {
		char s;
		int x, a;
		cin >> s >> x >> a;
		if (s == 'M') 
			update(1, 1, n, a, x);
		else {
			pair<int, pair<int, int>> ans = find(1, 1, n, a, x);
			if (ans.F == inf) {
				cout << -1 << endl;
			}
			else {
//				cout << ans.F << " " << ans.S.F << " " << ans.S.S << endl;
				cout << get_ans(ans.F, ans.S.F, ans.S.F, x) << endl;
			}
		}
	
	}
}

void run() {
	memset(seg, 127, sizeof(seg));
	query();
}

signed main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	run();
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Incorrect 2 ms 6492 KB Output isn't correct
3 Incorrect 3 ms 6492 KB Output isn't correct
4 Incorrect 82 ms 7732 KB Output isn't correct
5 Incorrect 69 ms 7424 KB Output isn't correct
6 Incorrect 74 ms 7368 KB Output isn't correct
7 Incorrect 74 ms 7600 KB Output isn't correct