답안 #83353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83353 2018-11-07T09:28:48 Z faceless Deda (COCI17_deda) C++17
140 / 140
451 ms 17084 KB
#include <bits/stdc++.h>
#define MP make_pair
#define F first
#define PB push_back
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int mod = (int)1e9 + 7;
const int maxn = 2e5 + 4;
const int inf = 1e9 + 1;

int seg[4 * maxn];

int get (int id, int L, int R, int l, int r, int x) {
	if (seg[id] > x)
		return -1;
	if (L == l and R == r) {
		if (L + 1 == R)
			return L;
		int mid = (L + R) >> 1;
		int ret = get (2 * id + 0, L, mid, L, mid, x);
		if (ret != -1)
			return ret;
		return get (2 * id + 1, mid, R, mid, R, x);
	}
	int ret = -1, mid = (L + R) >> 1;
	if (mid > l)
		ret = get (2 * id + 0, L, mid, l, min (mid, r), x);
	if (ret != -1)
		return ret;
	return get (2 * id + 1, mid, R, max (l, mid), r, x);
}

void change (int id, int L, int R, int idx, int x) {
	if (L + 1 == R) {
		seg[id] = x;
		return;
	}
	int mid = (L + R) >> 1;
	if (mid > idx)
		change (2 * id + 0, L, mid, idx, x);
	else
		change (2 * id + 1, mid, R, idx, x);
	seg[id] = min (seg[2 * id + 0], seg[2 * id + 1]);
}

int main (){
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		change (1, 1, n + 1, i, inf);
	for (int i = 0; i < q; i++) {
		char type;
		cin >> type;
		if (type == 'M') {
			int station, student;
			cin >> station >> student;
			change (1, 1, n + 1, student, station);
		}
		else {
			int number, age;
			cin >> number >> age;
			cout << get (1, 1, n + 1, age, n + 1, number) << '\n';
		}
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 464 KB Output is correct
3 Correct 11 ms 660 KB Output is correct
4 Correct 451 ms 7212 KB Output is correct
5 Correct 371 ms 9036 KB Output is correct
6 Correct 399 ms 13796 KB Output is correct
7 Correct 440 ms 17084 KB Output is correct