Cod sursa(job #1765960)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 27 septembrie 2016 10:24:18
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<cstdio>
#include<algorithm>
#define max_n 500001
#define f first
#define s second
using namespace std;
int i, n, k, a[max_n], cap, coada, sol, unde;
pair<int,int> cd[max_n];
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]);
    cap=1; coada=1; cd[1]=make_pair(a[1],1);
    for (i=2;i<k;i++) {
        while ((cap<=coada)&&(a[i]<cd[coada].f)) coada--;
        cd[++coada]=make_pair(a[i],i);
    }
    for (i=k;i<=n;i++) {
        while ((cap<=coada)&&(cd[cap].s<i-k+1)) cap++;
        if (cap>coada) cap=coada;
        while ((cap<=coada)&&(a[i]<cd[coada].f)) coada--;
        if (coada<cap) coada=cap;
        cd[++coada]=make_pair(a[i],i);
        if (cd[cap].f>sol) {sol=cd[cap].f; unde=i;}
    }
    printf("%d %d %d\n", unde-k+1, unde, sol);
    return 0;
}