답안 #82339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82339	2018-10-30T05:49:37 Z	fredbr	Deda (COCI17_deda)	C++17	60 / 140	4 ms	732 KB

deda

#include <bits/stdc++.h>

using namespace std;

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

class SegTree {
private:
	int n;
	int tree[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

60.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	4 ms	440 KB	Output is correct
4	Runtime error	2 ms	616 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	3 ms	636 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	2 ms	732 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	3 ms	732 KB	Execution killed with signal 11 (could be triggered by violating memory limits)