Submission #85659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
85659	2018-11-21T10:09:18 Z	heon	Deda (COCI17_deda)	C++11	140 / 140	142 ms	8232 KB

deda

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 200005;

int seg[MAXN * 4];

int query(int v, int l, int r, int L, int R, int val){
	if(l > R || r < L) return INT_MAX;
	if(l == r) return l;
	int m = (l + r) / 2;
	int ret = INT_MAX;
	if(seg[v * 2] <= val){
		ret = min(ret, query(v * 2, l, m, L, R, val));
		if(ret != INT_MAX) return ret; 
	}
	if(seg[v * 2 + 1] <= val) ret = min(ret, query(v * 2 + 1, m + 1, r, L, R, val));
	return ret;
}

void update(int v, int l, int r, int pos, int val){
	if(l == r) seg[v] = val;
	else{
		int m = (l + r) / 2;
		(pos <= m ? update(v * 2, l, m, pos, val) : update(v * 2 + 1, m + 1, r, pos, val));
		seg[v] = min(seg[v * 2], seg[v * 2 + 1]);
	}
}

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
  
	int n,q;
	cin >> n >> q;
	for(int i = 0; i <= n * 4; i++) seg[i] = INT_MAX;
	while(q--){
		char a;
		int b,c;
		cin >> a >> b >> c;
		if(a == 'M'){
			update(1, 1, n, c, b);
		}
		else{
			int res = query(1, 1, n, c, n, b);
			cout << (res == INT_MAX ? -1 : res) << "\n";
		}
	}
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	4 ms	588 KB	Output is correct
4	Correct	142 ms	8232 KB	Output is correct
5	Correct	113 ms	8232 KB	Output is correct
6	Correct	124 ms	8232 KB	Output is correct
7	Correct	124 ms	8232 KB	Output is correct