Cod sursa(job #1800711)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 7 noiembrie 2016 23:10:14
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <deque>
#include <climits>
using namespace std;

#ifdef INFOARENA
#define ProblemName "secventa"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

#define MAXN 500010
int v[MAXN], N, K;
deque<int> D;

void solve() {
	//D.push_back(0);
	int mmax = INT_MIN;
	int L = 0, R = K - 1;
	for (int i = 0; i < N; ++i) {
		while (!D.empty() && v[i] <= v[D.back()])
			D.pop_back();
		D.push_back(i);
		if (i - D.front() >= K)
			D.pop_front();
		if (i >= K - 1 &&
			v[D.front()] > mmax) {
			mmax = v[D.front()];
			L = i - K + 1;
			R = i;
		}
	}
	printf("%d %d %d\n", L + 1, R + 1, mmax);
}

const int MAXBUF = 10 * MAXN;
char buf[MAXBUF];

int main() {
	freopen(InFile, "r", stdin);
	freopen(OuFile, "w", stdout);
	scanf("%d%d", &N, &K); getchar();
	gets(buf);
	char *buff = buf;
	for (int i = 0; i < N; ++i) {
		v[i] = 0;
		int semn = 1;
		if (*buff == '-') {
			semn = -1;
			++buff;
		}
		for (; *buff >= '0' && *buff <= '9'; ++buff)
			v[i] = v[i] * 10 + (*buff) - '0';
		v[i] *= semn;
		++buff;
	}
	//for (int i = 0; i < N; ++i)
	//	scanf("%d", &v[i]);
	solve();
	return 0;
}