Submission #69392

#	Time	Username	Problem	Language	Result	Execution time	Memory
69392		KLPP	Editor (BOI15_edi)	C++14	63 / 100	585 ms	95392 KiB

edi

#include "stdio.h"
#include <iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
typedef std::set<int>::iterator sit;
int arr[400000];

int calculate(int x){
	if(arr[x]>=0)return x;
	stack<int> q;
	q.push(arr[x]);
	for(int i=x-1;i>0;i--){
		if(arr[i]>q.top()){
			q.pop();
		}else q.push(arr[i]);
		
		if(q.empty()){
			return calculate(i-1);
		}
	}
	return 0;
}
int main(){
	int n;
	cin>>n;
	//if(n<=5000){
	n++;
	arr[0]=0;
	for(int i=1;i<n;i++){
		cin>>arr[i];
	}
	/*int prev[n];
	bool active[n];
	for(int i=0;i<n;i++)prev[i]=-1;
	active[0]=true;
	map<pair<int,int> > s;
	for(int i=1;i<n;i++){
		active[i]=true;
		if(arr[i]>0)cout<<arr[i]<<endl;
		else{
			int pnt=i;
			for(int j=i-1;j>0;j--){
				if(arr[j]>arr[pnt]){
					if(active[j]){
						prev[i]=j;
						j=0;
						while(prev[pnt]!=-1){//cout<<pnt<<" "<<i<<endl;
							pnt=prev[pnt];
							active[pnt]=!active[pnt];
						}
					}
				}
			}
			int ans=0;
			for(int j=0;j<i;j++){
				if(arr[j]>0 && active[j])ans=arr[j];
			}cout<<ans<<endl;
		}
	}
	return 0;
	}
	int arr[n];
	stack<int> q;
	q.push(0);
	for(int i=0;i<n;i++){
		cin>>arr[i];
		if(arr[i]>0)q.push(arr[i]); 
		else q.pop();
		cout<<q.top()<<endl;
	}
	*/
	if(n<=6000){
		for(int i=1;i<n;i++)cout<<arr[calculate(i)]<<endl;
		return 0;
	}
	int minimo=0;
	for(int i=1;i<n;i++)minimo=min(minimo,arr[i]);
	if(minimo>=-1){
		stack<int> q;
		q.push(0);
		for(int i=1;i<n;i++){
			if(arr[i]>0)q.push(arr[i]); 
			else q.pop();
			cout<<q.top()<<endl;
		}
	}else{
		for(int i=1;i<n-1;i++)cout<<"1"<<endl;
		cout<<arr[calculate(n-1)]<<endl;
	}
	return 0;
}

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