Cod sursa(job #1428760)

Utilizator armageddon89_rAdrian D armageddon89_r Data 5 mai 2015 00:59:53
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
#include <cstdlib>

int deque[500000];
int v[500000];
const int smax = 4000000;
char s[smax];
int main()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);

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

	fgets(s, smax, stdin);
	char *p = s;
	v[0] = strtol(p, &p, 10);
	int l = 0;
	int r = 0;
	deque[l] = 0;
	int max = -30001;
	int pozmin = 0;

	for (int i = 1; i < n; i++)
	{
		v[i] = strtol(p, &p, 10);
		while (r >= l && v[i] < v[deque[r]])
		{
			r--;
		}

		deque[++r] = i;

		int val = deque[l];
		if (v[val] > max && i >= k - 1)
		{
			max = v[val];
			pozmin = i - k + 1;
		}

		if (i - val == k - 1)
			l++;
	}

	printf("%d %d %d\n", pozmin + 1, pozmin + k, max);

	return 0;
}