Cod sursa(job #565995)

Utilizator bogfodorBogdan Fodor bogfodor Data 28 martie 2011 15:49:26
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <deque>
#include <cstdio>
#define Lmax 500005

int n, k,maxim=-99999999,pi,pf;
int a[Lmax];using namespace std;

FILE *fin=freopen("secventa.in","r",stdin);
FILE *fout=freopen("secventa.out","w",stdout);

deque <int> c;
void functie()
{
    ifstream fin("secventa.in");
    fin>>n>>k;
    for(int i=0;i<n;i++)
    {
        fin>>a[i];
        if(!c.empty() && c.front()<=i-k)
            c.pop_front();
        while(!c.empty() && a[c.back()]>=a[i])
            c.pop_back();
        c.push_back(i);
        if(i>=k-1 && maxim<a[c.front()]){
            pi=c.back()-k+1;
            maxim=a[c.front()];
        }
    }

}

int main()
{
    functie();
    printf("%d %d %d\n", pi+1, pi+k, maxim);
    return 0;
}