Cod sursa(job #490454)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 6 octombrie 2010 16:54:21
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb

#include<deque>
#include<cstdio>
#include<fstream>

using namespace std;

#define m 500001

int v[m];
int n,k;
int st,dr;

void inline read () {
	
	ifstream in ("secventa.in");
	in>>n>>k;
	for(int i=1;i<=n;++i)
	in>>v[i];
	in.close();
	
	}
	
	int inline solve (){
		
		int dim=-1<<30;
		deque<int> q(1,1);
		for(int i=2;i<k;++i){
			for(;v[q.back()]>=v[i]&&!q.empty();q.pop_back());
			q.push_back(i);
			}
			for(int i=k;i<=n;++i){
				for(;v[q.back()]>=v[i]&&!q.empty();q.pop_back());
				q.push_back(i);
				if(v[q.front()]>dim){
					dim=v[q.front()];
					dr=i;
					st=1+i-k;
					}
					if(q.front()<2+i-k)
					q.pop_front();
				}
		
		return dim;}
		
		void inline write (int n){
			
			freopen ("secventa.out","w",stdout);
			printf("%d %d %d\n",st,dr,n);
			
			}

int main ()
{
	
	read ();
	write (solve ());
	
	return 0;}