Cod sursa(job #1764695)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 25 septembrie 2016 20:05:05
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<cstdio>
#include<stack>
#include<algorithm>
#define max_n 500001
#define f first
#define s second
using namespace std;
stack<pair<int,int> > mn;
int n, i, a[max_n], sol, unde, k;
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]);
    for (i=1;i<=k;i++) {
        while ((!mn.empty())&&(a[i]<(mn.top()).f)) mn.pop();
        mn.push(make_pair(a[i], i));
    }
    sol=(mn.top()).f; unde=k; ///unde=pozitie final
    for (i=k+1;i<=n;i++) {
        while ((!mn.empty())&&(a[i]<(mn.top()).f)) mn.pop();
        while ((!mn.empty())&&((mn.top()).s<i-k+1)) mn.pop();
        mn.push(make_pair(a[i], i));
        if ((mn.top()).f>sol) {sol=(mn.top()).f; unde=i;}
    }
    printf("%d %d %d", unde-k+1, unde, sol);
    return 0;
}