Cod sursa(job #749299)

Utilizator SzakatsSzakats Istvan Szakats Data 16 mai 2012 17:00:18
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

#ifdef _WIN32
#define TYPEOF decltype
#else
#define TYPEOF typeof
#endif

#define FOR(i,s,e) for(int i = s;i < e; i++)
#define TR(i, c) for(TYPEOF(c.begin()) i = c.begin(); i != c.end(); ++i)
#define TRS(i, c, ...) TR(__itr, c) { TYPEOF(*c.begin()) &i = *__itr;  __VA_ARGS__ }
#define TRP(f, s, c, ...) TR(__itr, c) { TYPEOF(c.begin()->first) &f = __itr->first; TYPEOF(c.begin()->second) &s = __itr->second;  __VA_ARGS__ }

char buf[20000000];
int a[500001];
int v[500001];

char *poz = buf;


inline bool is_space(char c) {
	//return isspace(c);
	return c == ' ' || c == '\n';
}

int read(char delim = ' ') {
	//while(is_space(*poz)) poz++;

	int k = 1;
	if(*poz == '-') {
		k = -1;
		poz++;
	}
	int t = (*poz - '0');
	poz++;

	char c = *poz;
	//while(!is_space(c)) {
	while(c != delim) {
		t = 10 * t + (c - '0');
		poz++;
		c = *poz;
	}

	poz++;	// specific

	return k * t;
}

int main()
{
#if 1
	freopen("secventa.in", "r", stdin);
#ifndef MY_STUFF
	freopen("secventa.out", "w", stdout);
#endif
#endif

	int n,k;

	fseek(stdin, 0, SEEK_END);
	int len = ftell(stdin);
	fseek(stdin, 0, SEEK_SET);
	fread(buf, 1, len, stdin);
	fclose(stdin);
	buf[len] = ' ';
	if(buf[len-1] == '\n') buf[len-1] = ' ';
	if(buf[len-2] == '\n') buf[len-2] = ' ';

	n = read();
	k = read('\n');

	int s = 0, e = -1, best = -40000, best_i;

	a[0] = 0;
	v[0] = read();

	FOR(i,1,k-1) {
		int c = read();

		while(e >= s) {
			if(v[e] >= c)
				e--;
			else
				break;
		}
		++e;
		a[e] = i;
		v[e] = c;
	}

	FOR(i,k-1,n) {
		int c = read();
		
		if(a[s] == i - k) {
			s++;
		}

		while(e >= s) {
			if(v[e] >= c)
				e--;
			else
				break;
		}
		++e;
		a[e] = i;
		v[e] = c;

		if(v[s] > best) {
			best = v[s];
			best_i = i;
		}
	}

	printf("%d %d %d\n", best_i+1 -k+1, best_i+1, best);

	return 0;
}