Submission #234431

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
234431	2020-05-24T08:36:19 Z	NONAME	Deda (COCI17_deda)	C++17	140 / 140	120 ms	3704 KB

deda

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

Subtask #1

140.0 / 140.0

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