Cod sursa(job #749290)

Utilizator SzakatsSzakats Istvan Szakats Data 16 mai 2012 16:38:40
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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__ }

int a[500001];
int v[500001];

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

	int n,k;

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

	//int s = 0, e = -1, best = -40000, best_i;
	int best = -40000, best_i;
	int *sa = a, *ea = sa-1;
	int *sv = v, *ev = sv-1;

	a[0] = 0;
	scanf("%d", &v[0]);

	FOR(i,1,k-1) {
		int c;
		scanf("%d", &c);

		if(*sa == i - k) {
			sa++, sv++;
		}

		while(ev >= sv) {
			if(*ev >= c)
				ev--, ea--;
			else
				break;
		}
		*(++ea) = i;
		*(++ev) = c;
	}

	FOR(i,k-1,n) {
		int c;
		scanf("%d", &c);
		
		if(*sa == i - k) {
			sa++, sv++;
		}

		while(ev >= sv) {
			if(*ev >= c)
				ev--, ea--;
			else
				break;
		}
		*(++ea) = i;
		*(++ev) = c;

		if(*sv > best) {
			best = *sv;
			best_i = i;
		}
	}

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

	return 0;
}