Submission #75344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
75344	2018-09-09T10:45:47 Z	FiloSanza	Deda (COCI17_deda)	C++14	140 / 140	594 ms	3700 KB

deda

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

struct segmentTree{
	const int nullval = 2e9;
	int S;
	vector<int> v;
	segmentTree(int s){
		S = (1<<((int)ceil(log2(s))+1)) - 1;
		v.resize(S, nullval);
	}

	inline int father(int pos){ return (pos-1)/2; }
	inline int left(int pos){ return (pos*2)+1; }
	inline int right(int pos){ return (pos+1)*2; }

	void update(int pos, int val){
		pos = pos + S/2;
		assert(v[pos] == nullval);
		v[pos] = val;

		while(pos != 0){
			pos = father(pos);
			v[pos] = min(v[left(pos)], v[right(pos)]);
		}
	}

	int solve(int pos, int val){
		while(pos < S/2){
			if(v[left(pos)] <= val)
				pos = left(pos);
			else
				pos = right(pos);
		}

		return pos - S/2;
	}

	int _query(int pos, int a, int b, int l, int val){
		if(b < l)
			return nullval;
		if(v[pos] > val)
			return nullval;
		if(a >= l)
			return solve(pos, val);

		int mid = (a + b)/2;
		return min(_query(left(pos), a, mid, l, val), _query(right(pos), mid+1, b, l, val));
	}

	int query(int pos, int val){
		int ans = _query(0, 0, S/2, pos, val);
		if(ans == nullval) return -1;
		else return ans;
	}

	void debug(){
		cout << "\n\n\nDEBUG\n\n\n";
		for(auto i : v) cout << i << " ";
		cout << "\n\n\nDEBUG\n\n\n";
	}
};

int main(){
	int N, Q;
	cin >> N >> Q;

	char c;
	int a, b;
	segmentTree tree(N);
	while(Q--){
		cin >> c >> a >> b;
		b--;
		if(c == 'M'){
			tree.update(b, a);
		}
		else{
			int ans = tree.query(b, a);
			cout << (ans == -1 ? -1 : ans+1) << "\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	380 KB	Output is correct
3	Correct	13 ms	424 KB	Output is correct
4	Correct	594 ms	3700 KB	Output is correct
5	Correct	519 ms	3700 KB	Output is correct
6	Correct	567 ms	3700 KB	Output is correct
7	Correct	581 ms	3700 KB	Output is correct