Submission #868157

#	Time	Username	Problem	Language	Result	Execution time	Memory
868157		oscar1f	Editor (BOI15_edi)	C++17	15 / 100	102 ms	45432 KiB

edi

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

struct sommet {
	int val,pere;
	vector<pair<int,int>> fils;
	unordered_map<int,int> valAre;
};

const int MAX_SOM=300*1000+5;
sommet arbre[MAX_SOM];
int nbOp,nbSom,nouv,pos,suiv,posMeil,trouve;

vector<pair<int,int>> effacer(vector<pair<int,int>> v,pair<int,int> p) {
	vector<pair<int,int>> r;
	for (auto i:v) {
		if (i!=p) {
			r.push_back(i);
		}
	}
	return r;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>nbOp;
	for (int iop=0;iop<nbOp;iop++) {
		cin>>nouv;
		if (nouv>0) {
			nbSom++;
			arbre[nbSom].val=nouv;
			arbre[nbSom].pere=pos;
			arbre[pos].valAre[nbSom]=0;
			arbre[pos].fils.push_back({0,nbSom});
			pos=nbSom;
		}
		else {
			nouv*=-1;
			trouve=0;
			for (int i=(int)arbre[pos].fils.size()-1;i>=0;i--) {
				if (trouve==0 and arbre[pos].fils[i].first<nouv) {
					trouve=1;
					suiv=arbre[pos].fils[i].second;
					arbre[pos].fils=effacer(arbre[pos].fils,{arbre[pos].valAre[suiv],suiv});
					arbre[pos].valAre[suiv]=nouv;
					arbre[pos].fils.push_back({arbre[pos].valAre[suiv],suiv});
					pos=suiv;
				}
			}
			if (trouve==0) {
				suiv=arbre[pos].pere;
				arbre[suiv].fils=effacer(arbre[suiv].fils,{arbre[suiv].valAre[pos],pos});
				arbre[suiv].valAre[pos]=nouv;
				arbre[suiv].fils.push_back({arbre[suiv].valAre[pos],pos});
				pos=suiv;
			}
		}
		cout<<arbre[pos].val<<"\n";
	}
	/*for (int i=0;i<=nbSom;i++) {
		cout<<i<<" "<<arbre[i].val<<" "<<arbre[i].pere<<endl;
	}*/
	return 0; 
}

• Subtask 1: 0 / 20
• Subtask 2: 15 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37