Cod sursa(job #2032509)

Utilizator refugiatBoni Daniel Stefan refugiat Data 5 octombrie 2017 09:49:01
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>
#include <deque>
using namespace std;
FILE*si=fopen("secventa.in","r");
FILE*so=fopen("secventa.out","w");
int v[500005];
int dp[500005];
int main()
{
    int n,k;
    fscanf(si,"%i %i",&n,&k);
    for(int i=1;i<=n;++i)
    {
        fscanf(si,"%i",&v[i]);
    }
    int st=1,fi=0;
    int pozi,minm=-1000000000;
    for(int i=1;i<=n;i++)
    {
        while(v[i]<v[dp[fi]]&&st<=fi)
            fi--;
        fi++;
        dp[fi]=i;
        if(i-dp[st]==k)
            st++;
        if(i>=k)
            if(minm<v[dp[st]])
            {
                pozi=i-k+1;
                minm=v[dp[st]];
            }
    }
    fprintf(so,"%i %i %i",pozi,pozi+k-1,minm);
    return 0;
}