제출 #1064010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064010		vjudge1	Deda (COCI17_deda)	C++17	140 / 140	344 ms	8020 KiB

deda

#include<bits/stdc++.h>
using namespace std;

class SegTree {
  private:
	vector<int> st;
	int sz;
	
	void update(int pos, int val, int id, int l, int r) {
		if (l == r) { st[id] = val; return; }
		int m = (l + r) >> 1;
		if (m >= pos) update(pos, val, id << 1, l, m);
		else update(pos, val, id << 1 | 1, m + 1, r);
		st[id] = min(st[id << 1], st[id << 1 | 1]);
	}
	
	int query(int val, int l, int r, int id, int tl, int tr) {
		if (r < tl || l > tr) return -1;
		if (l <= tl && tr <= r) {
			if (st[id] > val) return -1;
			if (tl == tr) return st[id] > val ? -1 : tl;
		}
		int m = (tl + tr) >> 1;
		int tmp = query(val, l, r, id << 1, tl, m);
		if (tmp != -1) return tmp;
		return query(val, l, r, id << 1 | 1, m + 1, tr);
	}
  public: 
	SegTree(int n) {
		st.assign(n << 2 | 1, 1e9 + 3);
		sz = n;
	}
	void update(int pos, int val) { update(pos, val, 1, 1, sz); }
	int query(int val, int l) { return query(val, l, sz, 1, 1, sz); }
};

int main() {
	int n, m; cin >> n >> m;
	SegTree s(n);
	while (m--) {
		char op; int a, b; 
		cin >> op >> a >> b;
		if (op == 'M') s.update(b, a);
		else cout << s.query(a, b) << '\n';
	}
	return 0;
}

• Subtask 1: 140 / 140