Submission #82448

#	Time	Username	Problem	Language	Result	Execution time	Memory
82448		fredbr	Deda (COCI17_deda)	C++17	0 / 140	10 ms	5452 KiB

deda

#include <bits/stdc++.h>

using namespace std;

const int maxn = 202020;
const int inf = 0x3f3f3f3f;

class SegTree {
private:
	int n;
	int tree[3*maxn];

	int build(int no, int l, int r)
	{
		if (l == r) return tree[no] = inf;
		int m = (l+r)/2;
		return tree[no] = min(build(no*2+1, l, m), build(no*2+2, m+1, r));
	}

	void upd(int no, int l, int r, int p, int val)
	{
		if (l == r) {
			tree[no] = val;
			return;
		}

		int m = (l+r)/2;

		if (p <= m) upd(no*2+1, l, m, p, val);
		else upd(no*2+2, m+1, r, p, val);

		tree[no] = min(tree[no*2+1], tree[no*2+2]);
	}

	int get(int no, int l, int r, int mpos, int val)
	{
		if (r < mpos) return inf;

		if (tree[no] > val) return inf;
		
		if (l == r) {
			return l;
		}

		int m = (l+r)/2;
		int v = get(no*2+1, l, m, mpos, val);

		if (v == inf) return get(no*2+2, m+1, r, mpos, val);
		return v;
	}

public:

	void init(int x) {
		n = x;
		// build(0, 1, n);
		fill(tree, tree+4*maxn, inf);
	}

	void upd(int pos, int val)
	{
		upd(0, 1, n, pos, val);
	}

	int query(int pos, int val)
	{
		int ans = get(0, 1, n, pos, val);
		if (ans == inf) return -1;
		return ans;
	}
};

SegTree seg = SegTree();

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	seg.init(n);

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

		if (op == 'M') {
			int pos, val;
			cin >> val >> pos;

			seg.upd(pos, val);
		}
		else {
			int pos, val;
			cin >> val >> pos;

			int ans = seg.query(pos, val);
			cout << ans << "\n";
		}
	}
}

• Subtask 1: 0 / 140