Cod sursa(job #137043)

Utilizator ScrazyRobert Szasz Scrazy Data 16 februarie 2008 19:43:21
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>

#define NM 500001
int a[NM];
long m[2*NM-1];
long n, k;
int max;
long pi, pj;

void init(long node, long e, long u)
{
    if (e==u)
	m[node]=e;
    else
    {
	init(2*node, e, (e+u)/2);
	init(2*node+1, (e+u)/2+1, u);
	if (a[m[2*node]]<=a[m[2*node+1]])
	    m[node]=m[2*node];
	else
	    m[node]=m[2*node+1];
    }
}

int query(long node, long e, long u, long i, long j)
{
    int p1, p2;

    if (u < i || e > j)
	return -1;
    if (i <= e && u <=j)
	return m[node];

    p1 = query(2*node, e, (e+u)/2, i, j);
    p2 = query(2*node+1, (e+u)/2+1, u, i, j);

    if (p1==-1)
	return p2;
    if (p2==-1)
	return p1;
    if (a[p1]<=a[p2])
	return p1;
    else
	return p2;
}

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

    scanf("%ld %ld", &n, &k);

    for (long i=0; i<n; ++i)
	scanf("%d", a+i);

    init(1,0,n-1);

    int t=0;
    max=a[query(1,0,n-1,0,k-1)];
    pi=0;pj=k-1;

    for (long i=1; i+k-1<n; ++i)
	if (a[t=query(1,0,n-1,i,i+k-1)]>max) {max=a[t]; pi=i; pj=i+k-1;} 

    printf("%ld %ld %d", pi+1, pj+1, max);

    fclose(stdin);
    fclose(stdout);

    return 0;
}