제출 #75338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75338		FiloSanza	Deda (COCI17_deda)	C++14	0 / 140	234 ms	18104 KiB

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)]);
		}
	}

	//per risolvere la query risalgo dalla foglia fino a che non trovo un nodo "accettabile"
	//dopo scendo a cercando di rimanere più a sx possibile
	int query(int pos, int val){
		pos = pos+S/2;
		int start = pos;
		if(v[pos] <= val) 								//il nodo da cui parto va già bene
			return pos - S/2;
		//risalgo
		pos = father(pos);
		while(true){
			//cout << pos << " " << v[pos] << "\n";
			if(v[pos] <= val && v[right(pos)] <= val){			//se ho trovato un valore accettabile che viene da DX
				break;
			}
			else if(pos == 0){									//se arrivo alla radice e non ho ancora trovato il nodo non c'è soluzione
				return -1;
			}

			pos = father(pos);
		}

		//cout << "parto dal nodo " << pos << "\n";
		pos = right(pos);
		//scendo per arrivare alla foglia
		while(pos < S/2){
			if(left(pos) >= start && v[left(pos)] <= val)
				pos = left(pos);
			else
				pos = right(pos);
		}
		//cout << pos << "\n\n";
		return pos - (S/2);
	}

	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;
	vector<int> ans(Q);
	int i=0;

	char c;
	int a, b;
	segmentTree tree(N);
	while(Q--){
		cin >> c >> a >> b;
		b--;
		if(c == 'M'){
			tree.update(b, a);
		}
		else{
			int x = tree.query(b, a);
			ans[i++] = (x == -1) ? -1 : x+1;
		}
	}

	for(int j=0; j<i; j++)cout << ans[j] << "\n";
}

• Subtask 1: 0 / 140