Submission #673311

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
673311	2022-12-20T07:13:44 Z	facug91	Deda (COCI17_deda)	C++17	140 / 140	89 ms	4424 KB

deda

/*
        By: facug91
        From:
        Name:
        Date: 20/12/2022
        Solution:
*/

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
#define endline std::endl
#define LOG(x) std::cout << "#" << (#x) << ": " << (x) << std::endl
#else
#define endline "\n"
#define LOG(x)
#endif

#define y0 dbnw9uddu0132dnd03dnqwuidg1o
#define y1 nd03dnqwuidg1odbnw9uddu0132d
const double EPS = 1e-9;
const double PI = 2.0 * acos(0.0);
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;

const int MAX_N = 2e5 + 5;
const int MAX_Q = 2e5 + 5;
const int MOD = 1e9 + 7;
const int invalid = 1e9 + 5;


/**
 * \brief Defines a class for a Segment Tree.
 *        State: untested.
 *        Ref: Competitive Programming 3, section 2.4.3
 *             https://cp-algorithms.com/data_structures/segment_tree.html
 *
 * \tparam ValueType Type of the elements.
 * \tparam MaxSize Maximum number of elements.
 */
class SegmentTreePointUpdateRangeQuery {
private:
	int n;
	int st[MAX_N * 4];


	int combine(int a, int b) {
		return min(a, b);
	}

	int query(int v, int tl, int tr, int l, int r, int val) {
		if (l > r || st[v] > val) return -2;
		if (tl == tr) return tl;

		int tm = (tl + tr) / 2;
		int left = query(v * 2, tl, tm, l, std::min(r, tm), val);
		if (left != -2) return left;
		return query(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, val);
	}

	void update(int v, int tl, int tr, int pos, int val) {
		if (tl == tr) st[v] = val;
		else {
			int tm = (tl + tr) / 2;
			if (pos <= tm) update(v * 2, tl, tm, pos, val);
			else update(v * 2 + 1, tm + 1, tr, pos, val);
			st[v] = combine(st[v * 2], st[v * 2 + 1]);
		}
	}

public:

	void build(int size, int val) {
		n = size;
		fill(st+1, st+n*4+1, invalid);
	}

	int query(int l, int r, int val) {
		return query(1, 0, n - 1, l, r, val);
	}

	void update(int idx, int val) {
		update(1, 0, n - 1, idx, val);
	}
};

int n, q, x, a, y, b;
char type;
SegmentTreePointUpdateRangeQuery st;


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

	cin >> n >> q;
	st.build(n, invalid);
	while (q--) {
		cin >> type;
		if (type == 'M') {
			cin >> x >> a;
			st.update(a - 1, x);
		} else if (type == 'D') {
			cin >> y >> b;
			cout << st.query(b - 1, n - 1, y) + 1 << endline;
		}
	}


	return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	75 ms	4424 KB	Output is correct
5	Correct	82 ms	2568 KB	Output is correct
6	Correct	84 ms	3564 KB	Output is correct
7	Correct	89 ms	4332 KB	Output is correct