Submission #570418

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
570418	2022-05-29T18:00:45 Z	saarang123	Deda (COCI17_deda)	C++17	60 / 140	1000 ms	7008 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) {
		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);
	auto q2 = query(v << 1|1, tm + 1, tr, l, r, y);
	//cout << tl << ' ' << tr << " range: " << q1[0] << ' ' << q2[0] << endl;
	if(q1[0] <= y)
		return q1;
	else
		return q2;
}

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

60.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	12 ms	6600 KB	Output is correct
4	Execution timed out	1093 ms	6756 KB	Time limit exceeded
5	Execution timed out	1056 ms	6860 KB	Time limit exceeded
6	Execution timed out	1075 ms	7008 KB	Time limit exceeded
7	Execution timed out	1070 ms	6804 KB	Time limit exceeded