Cod sursa(job #804244)

Utilizator legionarulCorneliu Zelea Codreanu legionarul Data 29 octombrie 2012 14:27:26
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
 # include <fstream>
 # include <cstring>
 # include <algorithm>
 # include <deque>
 # include <vector>
 
 # define dim 500005
 # define inf 999999999
 
 using namespace std;
 
 ifstream f("secventa.in");
 ofstream g("secventa.out");
 
 int a[ dim ];
 int n, k;
 int sol = -inf , 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 )
		 {
			 if ( sol < a[ q.front() ] )
			 {
				 inc = i - k + 1;
				 sf = i;
				 sol = a[ q.front() ];
			 }
			 
			 if ( q.front() == i - k + 1 )
				 q.pop_front();
		 }
	 }
	 g << inc << " " << sf << " " << sol << "\n";
 }
 
 int main()
 {
	 citire();
	 rezolva();
	 return 0;
 }