Submission #83353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
83353	2018-11-07T09:28:48 Z	faceless	Deda (COCI17_deda)	C++17	140 / 140	451 ms	17084 KB

deda

#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';
		}
	}
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	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