Cod sursa(job #422600)

Utilizator k_killerSzabo Krisztian k_killer Data 22 martie 2010 21:59:50
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<fstream>
#define maxn 500003
#define INFI 2000000000
using namespace std;
 
int n, k, st, dr;
int a[maxn], deq[maxn];
int minmax=-INFI, ri, rj;
 
int main()
{
    int i;
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>a[i];
    st=1, dr=0;
    for(i=1;i<=n;i++)
    {
        while(st<=dr && a[i]<=a[deq[dr]])
            dr--;
        deq[++dr]=i;
        if(deq[st]==i-k)
            st++;
        if(i>=k)
            if(a[deq[st]]>minmax)
            {
                minmax=a[deq[st]];
                ri=i-k+1;
                rj=i;
            }
    }
    fout<<ri<<" "<<rj<<" "<<minmax;
    return 0;
}