Cod sursa(job #804241)

Utilizator legionarulCorneliu Zelea Codreanu legionarul Data 29 octombrie 2012 14:18:55
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
 # include <fstream>
 # include <cstring>
 # include <algorithm>
 # include <deque>
 # include <vector>
 
 # define dim 500005
 
 using namespace std;
 
 ifstream f("secventa.in");
 ofstream g("secventa.out");
 
 int a[ dim ];
 int n, k;
 int sol, inc, sf;
 
 deque < int > q;
 
 void citire()
 {
	 int i;
	 
	 f >> n >> k;
	 for ( i = 1 ; i <= n ; i++ )
		 f >> a[ i ];
 }
 
 void rezolva()
 {
	 int i;
	 
	 q.push_front( 1 );
	 
	 for ( i = 2 ; i <= n ; i++ )
	 {
		 while ( !q.empty() && a[ i ] <= a[ q.back() ] )
			 q.pop_back();
		 
		 q.push_back( i );
		 
		 if ( i >= k )
		 {
			 inc = q.front();
			 sf = q.back();
			 sol = a[ q.front() ];
			 
			 if ( q.front() == i - k + 1 )
				 q.pop_front();
		 }
	 }
	 g << inc << " " << sf << " " << sol << "\n";
 }
 
 int main()
 {
	 citire();
	 rezolva();
	 return 0;
 }