Cod sursa(job #1604107)

Utilizator antanaAntonia Boca antana Data 17 februarie 2016 22:59:55
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include<deque>
#define MAX 500000
using namespace std;
deque<int>d;
int v[MAX+1];
int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    int n, k, i, bmin, pozmin;
    scanf("%d%d", &n, &k);
    for(i=1;i<=k;i++)
    {
        scanf("%d", &v[i]);
        while(!d.empty()&&v[d.back()]>=v[i])
            d.pop_back();
        d.push_back(i);
    }
    pozmin=1;
    bmin=v[d.front()];
    for(i=k+1;i<=n;i++)
    {
        scanf("%d", &v[i]);
        while(!d.empty()&&v[d.back()]>=v[i])
        {
            if(i-d.back()+1>=k)
            {
                if(v[i]>bmin)
                {
                    bmin=v[i];
                    pozmin=d.back();
                }
                else if(v[i]==bmin)
                {
                    if(d.back()<pozmin)
                        pozmin=d.back();
                }
            }
            d.pop_back();
        }
        d.push_back(i);
        if(d.back()-d.front()+1>=k)
            if(v[d.front()]>bmin)
            {
                bmin=v[d.front()];
                pozmin=d.front();
            }
        if(!d.empty()&&d.front()<=i-k)
            d.pop_front();
        if(d.back()-d.front()+1>=k)
            if(v[d.front()]>bmin)
            {
                bmin=v[d.front()];
                pozmin=d.front();
            }
    }
    i=pozmin;
    while(v[i]>=bmin&&i<=n)
        i++;
    printf("%d %d %d",pozmin, i-1, bmin);
    return 0;
}