Submission #570419

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
570419	2022-05-29T18:03:28 Z	saarang123	Deda (COCI17_deda)	C++17	140 / 140	530 ms	10740 KB

deda

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MXN = 200 * 1000 + 3;
array<int, 2> t[MXN << 2];
int n, q;

void update(int v, int tl, int tr, int pos, int val) {
	if(tl == tr)
		return t[v] = {val, pos}, void();
	int tm = (tl + tr) >> 1;
	if(pos <= tm)
		update(v << 1, tl, tm, pos, val);
	else
		update(v << 1|1, tm + 1, tr, pos, val);
	t[v] = min(t[v << 1], t[v << 1|1]);
}

void upd(int x, int val) { update(1, 1, n, x, val); }

array<int, 2> query(int v, int tl, int tr, int l, int r, int y) {
	if(l > tr || r < tl)
		return array<int, 2>{(int) 1e9 + 4, -1};
	if(tl == tr)
		return t[v];
	if(l <= tl && tr <= r) {
		if(t[v][0] > y)
			return array<int, 2>{(int) 1e9 + 4, -1};
		int tm = (tl + tr) >> 1;
		auto q1 = query(v << 1, tl, tm, l, r, y);
		if(q1[0] <= y)
			return query(v << 1, tl, tm, l, r, y);
		else
			return query(v << 1|1, tm + 1, tr, l, r, y);
	}
	int tm = (tl + tr) >> 1;
	auto q1 = query(v << 1, tl, tm, l, r, y);
	//cout << tl << ' ' << tr << " range: " << q1[0] << ' ' << q2[0] << endl;
	if(q1[0] <= y)
		return q1;
	else
		return query(v << 1|1, tm + 1, tr, l, r, y);
}

int query(int x, int y) {
	auto ok = query(1, 1, n, x, n, y);
	//cout << ok[0] << ' ' << ok[1] << '\n';
	if(ok[0] > y)
		return -1;
	return ok[1];
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    memset(t, 0x5f, sizeof t);
    cin >> n >> q;
    while(q--) {
    	char c; cin >> c;
    	if(c == 'M') {
    		int a, x;
    		cin >> x >> a;
    		upd(a, x);
    	} else {
    		int y, x;
    		cin >> y >> x;
    		cout << query(x, y) << '\n';
    	}
    }
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	3 ms	6484 KB	Output is correct
3	Correct	5 ms	6484 KB	Output is correct
4	Correct	530 ms	10740 KB	Output is correct
5	Correct	244 ms	10220 KB	Output is correct
6	Correct	297 ms	10576 KB	Output is correct
7	Correct	357 ms	10708 KB	Output is correct