Cod sursa(job #148526)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 4 martie 2008 14:51:38
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <utility>
using namespace std;

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

const long MAX = 500; //010;

char buf[7*MAX];
pair<long, long> Deque[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) ", Deque[i].f, Deque[i].s);
	printf("\n");
}

inline void push(pair<long, long> in) {
	while ( p<u && in.f-Deque[p].f>=k )
		++p;
	if ( in.s<Deque[p].s ) {
		while ( in.s<Deque[p].s && p<u ) 
			++p;
		Deque[p] = in;
		if ( p==u ) ++u;
	} else {
		while ( in.s<Deque[u-1].s )
			--u;
		Deque[u++] = in;
	}
//	print();
}

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

int main() {
	freopen("secventa.in", "r", stdin);
	scanf("%ld %ld\n", &n, &k);
	fgets(buf, 7*MAX, stdin);
	for (i=0; i<n; ++i) {
		sscanf(buf+nr, "%ld", &x);
        nr += nrc(x) + 1;
		push(mp(i, x));
		if ( i>=k-1 && Deque[p].s > m ) {
			st = i-k+1; dr = i;
			m = Deque[p].s;
		}
	}

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