Submission #1272432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272432		kakakakakak	Deda (COCI17_deda)	C++20	140 / 140	542 ms	5440 KiB

deda

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

const int maxn = 2e5 + 10, inf = 1e9 + 7;
int n, q, ar[maxn], seg[maxn << 2];

void input() {
	cin >> n >> q;
	fill(ar,ar + maxn,inf);
	fill(seg,seg + (maxn << 2),inf);
	n++;
}

void upd(int p, int x,int id = 1,int st = 1, int en = n) {
	if (st > p || en <= p)
		return;
	seg[id] = min(seg[id],x);
	if ((en - st) == 1)
		return;
	int lc = id << 1, rc = id << 1 | 1, mid = (st + en) >> 1;
	upd(p,x,lc,st,mid),upd(p,x,rc,mid,en);
}

int get(int l, int r,int id = 1,int st = 1, int en = n) {
	int lc = id << 1, rc = id << 1 | 1, mid = (st + en) >> 1;
	
	if (st >= r || en <= l)
		return inf;
	if (st >= l && en <= r) 
		return seg[id];
	return min(get(l,r,lc,st,mid),get(l,r,rc,mid,en));
}


int main() {
	ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	while (q--) {
		char type;
		cin >> type;
		if (type == 'M') {
			int x, p;
			cin >> x >> p;
			upd(p,x);
			ar[p] = x;
		}
		else {
			int y, l;
			cin >> y >> l;
			if (ar[l] <= y)
				cout << l << "\n";
			else if (get(l,n) > y)
				cout << -1 << "\n";
			else {
				int r = n;
				while (r - l > 1) {
					int mid = (r + l) / 2;
					if (get(l,mid) <= y) 
						r = mid;
					else
						l = mid;
				}
				cout << l << "\n";
			}
		}
	}

}

• Subtask 1: 140 / 140