Cod sursa(job #542422)

Utilizator EugenStoicaEugen Stoica EugenStoica Data 26 februarie 2011 13:14:47
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#define NM 500005

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");
		
int k,n,p,u,a[NM],dq[NM],maxim,st;

int main()
{ 
    maxim=-NM;
    p=u=1;
    fin>>n>>k; 
    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
	    while(a[i]<=a[dq[u]]&&p<=u) u--;
	    u++;dq[u]=i;
	    if(i>=k)
            if(maxim<a[dq[p]]) 
            {
                maxim=a[dq[p]];
                st=i;
            }
	    if(i>=k)
            while(dq[p]<=i-k+1&&p<=u) p++;
    }
	fout<<st-k+1<<' '<<st<<' '<<maxim;
	return 0;
}