Cod sursa(job #1233092)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 24 septembrie 2014 18:17:37
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
using namespace std;
int n, a[500010], b[500010], x=1, y=0, minim=-30010, poz, l, k, i;

inline int maxim(int a, int b){
    return (a>b?a:b);
}

int main(){
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    scanf("%d %d", &n, &k);
    for(i=1; i<=n; i++)
        scanf("%d", &a[i]);
    x=1;
    y=0;
    for(i=1; i<=n; i++)
    {
        while(x<=y && a[i]<=a[ b[y] ])
            y--;
        b[++y]=i;
        if(i>=k)
        if(minim<a[ b[x] ])
        {
            minim=a[ b[x] ];
            poz=b[x];
        }
        if(b[x]==i-k+1)
            x++;
    }
    l=poz;
    while(a[l-1]>=minim && l>1)
        l--;
    printf("%d %d %d\n", l, maxim(l+k-1, poz), minim);
    return 0;
}