Cod sursa(job #1016843)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 26 octombrie 2013 20:22:58
Problema Secventa Scor 100
Compilator cpp Status done
Runda pq Marime 1.6 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define NMAX 500001
#define dim 8192
#define T (u >> 1)
#define L (u << 1)
#define R (L | 1)

int i, n, N, K, dr;
int left, st;
int MX;

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

inline void cit(int &x) {
    x = 0;
    mins = false;
    while ((ax[pz] < '0' || ax[pz] > '9') && ax[pz] != '-')
        if (++pz == dim)
            fread (ax, 1, dim, stdin), pz = 0;
    if (ax[pz] == '-') {
        mins = 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 (mins)
        x *= -1;
}

int poz[NMAX];
int v[NMAX];
int H[NMAX];

void upheap(int u) {
	while (u != 1 && v[H[u]] < v[H[T]]) swap(H[u], H[T]), poz[H[u]] = u, poz[H[T]] = T, u = T;
}

void downheap(int u) {
	while (1) {
		int m = u;
		if (L <= n && v[H[L]] < v[H[m]]) m = L;
		if (R <= n && v[H[R]] < v[H[m]]) m = R;
		if (m == u) 
			break;
		swap(H[u], H[m]);
		poz[H[u]] = u;
		poz[H[m]] = m;
		u = m;
	}
}

int main() {
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	cit(N); cit(K);
	left = 1;
	MX = -30001;
	for (i = 1; i <= N; ++i) {
		cit(v[i]);
		H[++n] = i;
		poz[i] = n;
		upheap(n);
		if (i >= K){
			if (v[H[1]] > MX) 
				st = i - K + 1, dr = i, MX = v[H[1]];
			int u = poz[i - K + 1];
			swap(H[u], H[n]);
			poz[H[u]] = u;
			poz[H[n]] = n;
			--n;
			downheap(u);
		}
	}
	printf("%i %i %i", st, dr, MX);
	return 0;
}