Submission #736550

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
736550	2023-05-05T23:00:23 Z	bane	Deda (COCI17_deda)	C++17	140 / 140	822 ms	7104 KB

deda

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

const int maxN = (int)1e5 * 2;
int n, q, x, y;
class SegmentTree{
	public:
	int Seg[maxN * 3];
	void init(int l = 1, int r = n,int k = 1){
		if (l == r){
			Seg[k] = (int)1e9 + 9;
			return;
		}
		init(l,(l+r)/2,k*2);
		init((l+r)/2+1,r,k*2+1);
		Seg[k] = (int)1e9 + 9;
	}
	void upd(int pos, int val, int l = 1, int r = n, int k = 1){
		if (l == r){
			Seg[k] = val;
			return;
		}
		int md = (l + r) >> 1;
		if (pos <= md){
			upd(pos,val,l,md,k * 2);
		}else{
			upd(pos,val,md+1,r,k*2+1);
		}
		Seg[k] = min(Seg[k * 2], Seg[k * 2 + 1]);
	}
	int query(int a, int b, int l = 1, int r = n, int k = 1){
		if (l >= a && r <= b)return Seg[k];
		if (r < a || l > b)return (int)1e9 + 1;
		int md = (l + r) >> 1;
		return min(query(a,b,l,md,k*2), query(a,b,md+1,r,k*2+1));
	}
	int find(int Y, int B){
		int low = B, high = n;
		int ans = -1;
		while(low <= high){
			int md = (low + high) >> 1;
			if (query(B,md) <= Y){
				high = md - 1;
				ans = md;
			}else{
				low = md + 1;
			}
		}
		return ans;
	}
};


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	SegmentTree Seg;
	Seg.init();
	while(q--){
		char C;
		cin >> C >> x >> y;
		if (C == 'M'){
			Seg.upd(y,x);
		}else{
			cout<<Seg.find(x,y)<<'\n';
		}
	}
	return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	8 ms	2728 KB	Output is correct
4	Correct	822 ms	7036 KB	Output is correct
5	Correct	485 ms	6660 KB	Output is correct
6	Correct	581 ms	6972 KB	Output is correct
7	Correct	653 ms	7104 KB	Output is correct