Submission #876603

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
876603	2023-11-22T05:24:38 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	655 ms	8156 KB

deda

#include <bits/stdc++.h>

using namespace std;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define F first
#define S second

const int maxn = 2e5 + 100;
const int NN = 2e5 + 1;
int seg[4 * maxn];

void upd(int id, int s, int e, int l, int r, int x){
	if(l <= s && e <= r){
		seg[id] = x;
		return;
	}
	if(r <= s || e <= l){
		return;
	}
	int mid = (s + e) / 2;
	upd(id * 2, s, mid, l, r, x);
	upd(id * 2 + 1, mid, e, l, r, x);
	seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
}

int get(int id, int s, int e, int l, int r){
	if(l <= s && e <= r){
		return seg[id];
	}
	if(r <= s || e <= l){
		return 1e9 + 1;
	}
	int mid = (s + e) / 2;
	return min(get(id * 2, s, mid, l, r), get(id * 2 + 1, mid, e, l, r));
}

void solve(int y, int b){
	int lo = b, hi = NN;
	if(get(1, 0, NN, b, NN) > y){
		cout << -1 << "\n";
		return;
	}
	while(hi - lo > 1){
		int mid = (hi + lo) / 2;
		if(get(1, 0, NN, lo, mid) <= y){
			hi = mid;
		}
		else{
			lo = mid;
		}
	}
	cout << lo << "\n";
}

int main(){
	fast_io;
	memset(seg, 63, sizeof seg);
//	cout << seg[1] << "\n";
	int n, q;
	cin >> n >> q;
	for(int i = 0; i < q; i++){
		char c; cin >> c;
		if(c == 'M'){
			int x, a;
			cin >> x >> a;
			upd(1, 0, NN, a, a + 1, x);
		}
		if(c == 'D'){
			int y, b;
			cin >> y >> b;
			solve(y, b);
		}
	}
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3420 KB	Output is correct
2	Correct	2 ms	3420 KB	Output is correct
3	Correct	14 ms	3644 KB	Output is correct
4	Correct	655 ms	8156 KB	Output is correct
5	Correct	613 ms	7464 KB	Output is correct
6	Correct	617 ms	7828 KB	Output is correct
7	Correct	646 ms	8028 KB	Output is correct