답안 #234431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234431 2020-05-24T08:36:19 Z NONAME Deda (COCI17_deda) C++17
140 / 140
120 ms 3704 KB
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 100500
#define oo ll(1e16)
#define ft first
#define sd second
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
using namespace std;
typedef long long ll;
typedef long double ld;

int n, q;
int t[8 * N];

void build(int v, int l, int r) {
	t[v] = 2e9;
	if (l >= r)
		return;

	int md = (l + r) >> 1;

	build(v + v, l, md);
	build(v + v + 1, md + 1, r);
}

void upd(int v, int l, int r, int ps, int vl) {
	if (l == r) {
        t[v] = vl;
        return;
	}

	int md = (l + r) >> 1;

	if (ps <= md) upd(v + v, l, md, ps, vl);
		else upd(v + v + 1, md + 1, r, ps, vl);

	t[v] = min(t[v + v], t[v + v + 1]);
}

int f(int v, int l, int r, int tl, int tr, int vl) {
	if ((l > r) || (tl > r) || (l > tr) || (t[v] > vl))
		return -1;

    if (l == r)
		return l;

	int md = (l + r) >> 1;

	int c = -1;

    if (t[v + v] <= vl) c = f(v + v, l, md, tl, tr, vl);
	if (c == -1)
		c = f(v + v + 1, md + 1, r, tl, tr, vl);

	return c;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    in("input.txt");

	cin >> n >> q;

	build(1, 0, n - 1);

	while (q--) {
		char c;
		cin >> c;

		if (c == 'D') {
			int x, y;
			cin >> x >> y;
			y--;
			int rs = f(1, 0, n - 1, y, n - 1, x);

			cout << (rs == -1 ? -1 : rs + 1) << el;
		}

		if (c == 'M') {
			int x, y;
			cin >> x >> y;
			y--;

			upd(1, 0, n - 1, y, x);
		}
	}
}

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 109 ms 3704 KB Output is correct
5 Correct 108 ms 2296 KB Output is correct
6 Correct 115 ms 3424 KB Output is correct
7 Correct 120 ms 3624 KB Output is correct