View difference between Paste ID: EaFwYr9S and XwuxK5vU
SHOW: | | - or go back to the newest paste.
1
#include<fstream>
2
#include<vector>
3
#include<algorithm>
4
#include<stack>
5
using namespace std;
6-
/*
6+
7
ifstream in("solar.in");
8
ofstream out("solar.out");
9-
*/
9+
10
//declare stacks and N and some other variables to check wheather the first
11
// of the last value fits out criteria
12
int N;
13
stack<int>max_from_startpoint;
14
stack<int> values;
15
int max_val,min_val;
16
int first_val=0,last_val=-1;
17
18
void Read_and_find_mins_to_here(){
19
	in>>N;
20
	//read the values and find the minimun one up to a certain point
21
	for(int i=0; i<N; i++){
22
		int val;
23
		in>>val;
24
		if(i==0){
25
			max_from_startpoint.push(val);
26
			values.push(val);
27
			min_val=max_val=val;
28
		}
29
		else{
30
			int curmax=max(max_from_startpoint.top(),values.top());
31
			max_from_startpoint.push(curmax);
32
			values.push(val);
33
			//den xreiazetai na alla3w tin timi toy afoy den 8a to 3anaxrisimopoiisw
34
			if(val<min_val){
35
				first_val=-1;
36
			}
37
			if(val>max_val){
38
				max_val=val;
39
				if(i==N-1){
40
					last_val=0;
41
				}
42
			}
43
		}
44
	}
45
}
46
47
//run through the two stacks to find max values up 
48
//to a certain point and then check if the values.top()
49
//satisfies the given condition
50
void Find_solution(){
51
	//prwta elegxw to last_val
52
	if(last_val==0){
53
			out<<max_val<<'\n';
54
			return;
55
	}
56
	//meta ta eswterika
57
	int minc=values.top();
58
	int minprev=minc;
59
	values.pop();
60
	max_from_startpoint.pop();
61
	while(!values.empty()){
62
		minc=min(values.top(),minc);
63
		//out<<values.top()<<' '<<minprev<<' '<<max_from_startpoint.top()<<'\n';
64
		if(minprev>values.top() && max_from_startpoint.top()<values.top()){
65
			out<<values.top();
66
			break;
67
		}
68
		minprev=minc;
69
		values.pop();
70
		max_from_startpoint.pop();
71
	}
72
	if(values.empty()){
73
		//kai an den exw brei kati mexri edw elegxw kai to first_val
74
		if(first_val==0){
75
			out<<min_val<<'\n';
76
			return;
77
		}
78
		out<<"NOT FOUND";
79
	}
80
}
81
82
int main(){
83
	Read_and_find_mins_to_here();
84
	Find_solution();
85
	return 0;
86
}