Cod sursa(job #148542)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 4 martie 2008 15:21:29
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <cstdio>
#include <utility>
using namespace std;

#define mp make_pair
#define f first
#define s second
#define __debug__

#ifdef __debug__
const long MAX = 5000;
#else
const long MAX = 500010;
#endif

char buf[7*MAX];
long  Dequef[MAX], Deques[MAX];
long p,u;
long n,k,i,x;
long st, dr, m=-0x3f3f3f;
long nr;

void print() {
	for (long i=p; i<u; ++i)
		printf("(%ld %ld) ", Dequef[i], Deques[i]);
	printf("\n");
}

inline void push(long inf, long ins) {
	while ( p<u && inf-Dequef[p]>=k )
		++p;
	if ( ins<Deques[p] ) {
		while ( ins<Deques[p] && p<u ) 
			++p;
		Dequef[p] = inf; Deques[p] = ins;
		if ( p==u ) ++u;
	} else {
		while ( ins<Deques[u-1] )
			--u;
		Deques[u] = ins;
		Dequef[u++] = inf;
	}
//	print();
}

inline long nrc(long x) {
	long ret = 0;
    if ( x<=0 ) ret++, x=-x;
    for (; x; x/=10) ret++;
    return ret;
}

bool ok;

int main() {
	freopen("secventa.in", "r", stdin);
	scanf("%ld %ld\n", &n, &k);
	fgets(buf, 7*MAX, stdin);
	for (i=0; i<k-1; ++i) {
		for (ok=0; (buf[nr]>'9' || buf[nr]<'0') && buf[nr]!='-'; ++nr);
        if ( buf[nr]=='-' )
	        ++nr, ok=1;
		for (x=0; buf[nr]<='9' && buf[nr]>='0'; ++nr)
			x = x*10 + buf[nr]-'0';
		push(i, x * (ok)?-1:1);
	}
	for ( i=k-1; i<n; ++i) {
   		for (ok=0; (buf[nr]>'9' || buf[nr]<'0') && buf[nr]!='-'; ++nr);
        if ( buf[nr]=='-' )
	        ++nr, ok=1;
		for (x=0; buf[nr]<='9' && buf[nr]>='0'; ++nr)
			x = x*10 + buf[nr]-'0';
		push(i, x);
		if ( Deques[p] > m ) {
			st = i-k+1; dr = i;
			m = Deques[p];
		}
	}

	fprintf(fopen("secventa.out", "w"), "%ld %ld %ld\n", st+1, dr+1, m);
	return 0;
}