Cod sursa(job #2033897)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 7 octombrie 2017 11:44:02
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
#include <cstdio>
#define DIM 1000000
#define MAXN 500041
using namespace std;

char buff[DIM];
int curs;
/// http://tinyurl.com/parsare-c
void adv()
{
    curs++;
    if (curs >= DIM) {
        fread(buff, 1, DIM, stdin);
        curs = 0;
    }
}

int getInt()
{
    int nr = 0, semn = 1;
    while (!(buff[curs] >= '0' && buff[curs] <= '9')) {
        if (buff[curs] == '-')
            semn = -1;
        adv();
    }
    while (buff[curs] >= '0' && buff[curs] <= '9') {
        nr = nr*10 + buff[curs] - '0';
        adv();
    }
    return semn * nr;
}

int n, k;
int a[MAXN];
int deck[MAXN], st, dr = -1;
int maxim = -30041, phi;

void add(int val, int pos)
{
    while (st <= dr && val <= a[deck[dr]])
        dr--;
    deck[++dr] = pos;
}

int get(int pos)
{
    while (st <= dr && deck[st] <= pos - k)
        st++;
    return a[deck[st]];
}

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);

    fread(buff, 1, DIM, stdin);

    n = getInt();
    k = getInt();
    for (int i = 1; i <= n; i++)
        a[i] = getInt();
    for (int i = 1; i <= n; i++) {
        add(a[i], i);
        if (i >= k) {
            int crt = get(i);
            if (crt > maxim) {
                maxim = crt;
                phi = i;
            }
        }
    }
    cout << phi-k+1 << " " << phi << " " << maxim;
    return 0;
}