Cod sursa(job #1653975)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 16 martie 2016 18:56:57
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <cstdio>
#define MAXN 500050

using namespace std;

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

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 main()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);

	scanf("%d %d", &n, &k);
	st = 1; dr = 0;
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
    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;
}