oj.uz

Submission #69392

# Submission time Handle Problem Language Result Execution time Memory
69392 2018-08-20T18:31:18 Z KLPP Editor (BOI15_edi) C++14
63 / 100
 585 ms 95392 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 29 ms 496 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 506 ms 2584 KB Output is correct
6 Correct 2 ms 2584 KB Output is correct
7 Correct 13 ms 2584 KB Output is correct
8 Correct 2 ms 2584 KB Output is correct
9 Correct 12 ms 2584 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 5428 KB Output is correct
2 Correct 560 ms 7040 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 7040 KB Output is correct
2 Correct 353 ms 7040 KB Output is correct
3 Correct 512 ms 95392 KB Output is correct
4 Correct 585 ms 95392 KB Output is correct
5 Correct 565 ms 95392 KB Output is correct
6 Correct 536 ms 95392 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 29 ms 496 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 506 ms 2584 KB Output is correct
6 Correct 2 ms 2584 KB Output is correct
7 Correct 13 ms 2584 KB Output is correct
8 Correct 2 ms 2584 KB Output is correct
9 Correct 12 ms 2584 KB Output is correct
10 Correct 534 ms 5428 KB Output is correct
11 Correct 560 ms 7040 KB Output is correct
12 Correct 268 ms 7040 KB Output is correct
13 Correct 353 ms 7040 KB Output is correct
14 Correct 512 ms 95392 KB Output is correct
15 Correct 585 ms 95392 KB Output is correct
16 Correct 565 ms 95392 KB Output is correct
17 Correct 536 ms 95392 KB Output is correct
18 Incorrect 538 ms 95392 KB Output isn't correct
19 Halted 0 ms 0 KB -