Submission #876603

#	Time	Username	Problem	Language	Result	Execution time	Memory
876603		vjudge1	Deda (COCI17_deda)	C++17	140 / 140	655 ms	8156 KiB

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 / 140