Cod sursa(job #189626)

Utilizator thebest001Neagu Rares Florian thebest001 Data 16 mai 2008 13:03:27
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <cctype>
#include <cstring>
#include <deque>
using namespace std;

#define mp make_pair
#define pb push_back
#define x first
#define i second

#define MAX_N 500001
#define INF 0x3f3f3f3f

int A[MAX_N], N, K;
char S[MAX_N * 7];
deque <pair<int,int> > Q;

void read(void);
void solve(void);

int main()
{
    freopen("secventa.in","rt", stdin);
    freopen("secventa.out","wt", stdout);
    read();
    solve();
}

void read()
{
    int semn = 1, aux = 0, k = 0;

    gets(S);
    for(int i = 0; S[i] != 0; ++i)
    {
        if(isdigit(S[i]))
            aux = aux * 10 + S[i] - '0';
        if(S[i] == ' ')
        {
            N = aux;
            aux = 0;
        }
    }
    K = aux;
    aux = 0;

    gets(S);
    for(int i = 0; S[i] != 0; ++i)
    {
        if(S[i] == '-')
            semn = -1;
        if(isdigit(S[i]))
            aux = aux*10 + S[i] - '0';
        if(S[i] == ' ')
        {
            A[++k] = aux * semn;
            aux = 0;
            semn = 1;
        }
    }
    A[N] = aux;
}

void solve()
{
    int T = -INF, poz;
    for(int i = 1; i <= N; ++i)
    {
        while(!Q.empty() && Q.back().x >= A[i]) Q.pop_back();

        Q.pb(mp(A[i],i));
        while(!Q.empty() && i - Q.front().i >= K) Q.pop_front();
        if(i >= K && Q.front().x > T)
        {
            T = Q.front().x;
            poz = i;
        }
    }
    printf("%d %d %d\n",poz - K + 1, poz, T);
}