oj.uz

답안 #876603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876603 2023-11-22T05:24:38 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 655 ms 8156 KB 
#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

# 결과 실행 시간 메모리 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