Cod sursa(job #975331)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 19 iulie 2013 20:10:24
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
using namespace std;

#define NMAX 500001
#define dim 8192

int i, N, K, Q;
int Start = 1, End;
int st, dr, ANS = -30001;
int minus;

int v[NMAX];
int Deque[NMAX];

int x;
char ax[dim];
int pz;

inline void cit(int &x) {
    x = 0;
	minus = false;
    while (ax[pz] < '0' || ax[pz] > '9')
        if (++pz == dim)
            fread (ax, 1, dim, stdin), pz = 0;
	if (ax[pz] == '-') {
		minus = true;
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	}
    while (ax[pz] >= '0' && ax[pz] <= '9') {
        x = x * 10 + ax[pz] - '0';
        if (++pz == dim)
            fread (ax, 1, dim, stdin), pz = 0;
    }
	if (minus) 
		x *= -1;
}

void Insert(int i) {
	while (Start <= End && v[i] <= v[Deque[End]]) --End;
	Deque[++End] = i;
}

int Query(int p) {
	while (Start <= End && Deque[Start] < p) ++Start;
	return v[Deque[Start]];
}

int main() {
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	cit(N); cit(K);
	for (i = 1; i <= N; ++i) {
		cit(v[i]);
		Insert(i);
		if (i >= K) {
			Q = Query(i - K + 1);
			if (Q > ANS) 
				ANS = Q, st = i - K + 1, dr = i;
		}
	}
	printf("%i %i %i\n", st, dr, ANS);
	return 0;
}