Submission #82340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
82340	2018-10-30T05:50:09 Z	fredbr	Deda (COCI17_deda)	C++17	140 / 140	135 ms	3560 KB

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

	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

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	4 ms	508 KB	Output is correct
4	Correct	135 ms	3560 KB	Output is correct
5	Correct	127 ms	3560 KB	Output is correct
6	Correct	128 ms	3560 KB	Output is correct
7	Correct	126 ms	3560 KB	Output is correct