Cod sursa(job #1654015)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 16 martie 2016 19:22:35
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <cstdio>
#define MAXN 500050
#define DIM 1000050

using namespace std;

int a[MAXN], maxi = -999999999, poz, n, k;
int deck[MAXN], st, dr, nq;
char buf[DIM];

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

int get(int ind)
{
	while (deck[st]-ind >= k) st++;
    return a[deck[st]];
}

int read()
{
    int nr = 0;
    int sign = 1;
    while (buf[nq] < '0' || buf[nq] > '9') {
		if (buf[nq] == '-') sign = -1;
		nq++;
		if (nq == DIM)
			fread(buf, sizeof buf[0], DIM, stdin), nq = 0;
    }
    while (buf[nq] >= '0' && buf[nq] <= '9') {
        nr = nr*10 + buf[nq++]-'0';
        if (nq == DIM)
			fread(buf, sizeof buf[0], DIM, stdin), nq = 0;
    }
    return nr*sign;
}

int main()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	fread(buf, sizeof buf[0], DIM, stdin);

    n = read();
    k = read();

	st = 1; dr = 0;
	for (int i = 1; i <= n; i++)
		a[i] = read();
    for (int i = n; i > n-k+1; i--)
		add(i);
    for (int i = n-k+1; i >= 1; i--) {
		add(i);
        int val = get(i);
        if (val >= maxi) {
			maxi = val;
            poz = i;
        }
    }
    printf("%d %d %d", poz, poz+k-1, maxi);

    return 0;
}