Cod sursa(job #137053)

Utilizator ScrazyRobert Szasz Scrazy Data 16 februarie 2008 20:09:49
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
//O(n*lg(n))

#include <cstdio>
#include <cstring>

#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;
}


/*void add(char buf[8]) 
{  
    for (j = (buf[0] == '-' ? 1 : 0), u = 0; '0' <= buf[j] && buf[j] <= '9'; ++j)  
	u = u * 10 + (buf[j] - '0');  
} 
*/

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);
    
    char buf[8];
   
    for (long i = 0; i < n; ++i) 
    {  
	scanf(" %s", buf);  
	int u=0;
        for (int j = (buf[0] == '-' ? 1 : 0), u = 0; '0' <= buf[j] && buf[j] <= '9'; ++j)  
            u = u * 10 + (buf[j] - '0');  
        a[i] = buf[0] == '-' ? -u : u;  
    }  
    */

    long semn=0, aux, i;  
    char sir[2000024];  
    fgetc(stdin);  
    fgets(sir, 2000024,stdin);  
    aux=strlen(sir);  
    int nr=0; 
    
    for (i=0; i<aux; i++)  
    {  
	if (sir[i]=='-') semn=1;  
	if (sir[i]>='0' && sir[i]<='9')  
	{     
	    a[nr]=a[nr]*10+sir[i]-'0';  
	}  
	if (sir[i]==' ' && semn)  a[nr]*=-1, semn=0;  
	if (sir[i]==' ') nr++;  
    }  
    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;
}