Cod sursa(job #1728992)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 13 iulie 2016 23:20:50
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

#define INF (1<<30)
#define mod 666013

using namespace std;

int n, k, i, j, x, mx, a, v[500005];
char s[10000005];
deque <int> d;

int getNumber()
{
    int x=0;
    int mns=1;
    i++;
    while(s[i]!=' ')
    {
        if(s[i]=='-')
            mns=-1;
        else
            x=x*10+s[i]-'0';
        i++;
    }
    return x*mns;
}

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    scanf("%d%d\n", &n, &k);
    gets(s+1);
    i=0;
    for(j=1;j<=n;j++)
        v[j]=getNumber();

    mx=-INF;
    for(i=1;i<=n;i++)
    {
        while(!d.empty()&&v[i]<=v[d.back()])
            d.pop_back();
        d.push_back(i);
        x=d.front();
        if(i-d.front()>=k)
            d.pop_front();
        if(i>=k&&v[d.front()]>mx)
        {
            mx=v[d.front()];
            a=i;
        }
    }
    printf("%d %d %d", a-k+1, a, mx);
    return 0;
}