Submission #44295

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44295	2018-03-31T09:41:27 Z	JustInCase	Deda (COCI17_deda)	C++17	140 / 140	229 ms	17224 KB

deda

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int32_t MAX_N = 2e5 + 5;
const int32_t INF = 1e9 + 5;

class SegmentTree {
private:
	int32_t treeSize, data[4 * MAX_N];
	
	void Build(int32_t node, int32_t low, int32_t high) {
		if(low == high) {
			data[node] = INF;
			return;
		}

		int32_t mid = (low + high) / 2;
		Build(2 * node, low, mid);
		Build(2 * node + 1, mid + 1, high);

		data[node] = min(data[2 * node], data[2 * node + 1]);
	}

	void Update(int32_t node, int32_t low, int32_t high, int32_t qInd, int32_t qVal) {
		if(low > qInd || high < qInd) {
			return;
		}
		else if(low == qInd && high == qInd) {
			data[node] = qVal;
			return;
		}

		int32_t mid = (low + high) / 2;
		Update(2 * node, low, mid, qInd, qVal);
		Update(2 * node + 1, mid + 1, high, qInd, qVal);

		data[node] = min(data[2 * node], data[2 * node + 1]);
	}

	int32_t Query(int32_t node, int32_t low, int32_t high, int32_t qLow, int32_t qVal) {
		if(high < qLow || data[node] > qVal) {
			return -1;
		}
		else if(low == high) {
			if(data[node] <= qVal) {
				return low;
			}
			else {
				return -1;
			}
		}

		int32_t mid = (low + high) / 2;
		
		int32_t ansLeft = Query(2 * node, low, mid, qLow, qVal);
		if(ansLeft != -1) {
			return ansLeft;
		}

		return Query(2 * node + 1, mid + 1, high, qLow, qVal);
	}

public:
	void Init(int32_t n) {
		treeSize = n;
		Build(1, 1, treeSize);
	}

	void Update(int32_t ind, int32_t val) {
		Update(1, 1, treeSize, ind, val);
	}

	int32_t Query(int32_t low, int32_t val) {
		return Query(1, 1, treeSize, low, val);
	}
};

SegmentTree segTree;

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

	int32_t n, q;
	cin >> n >> q;
	
	segTree.Init(n);

	for(int32_t i = 1; i <= q; i++) {
		char type;
		cin >> type;

		if(type == 'M') {
			int32_t x, a;
			cin >> x >> a;

			segTree.Update(a, x);
		}
		else {
			int32_t y, b;
			cin >> y >> b;

			cout << segTree.Query(b, y) << endl;
		}
	}

	return 0;
}

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	376 KB	Output is correct
3	Correct	4 ms	564 KB	Output is correct
4	Correct	123 ms	7148 KB	Output is correct
5	Correct	129 ms	9040 KB	Output is correct
6	Correct	140 ms	13732 KB	Output is correct
7	Correct	229 ms	17224 KB	Output is correct