Cod sursa(job #216240)

Utilizator ProtomanAndrei Purice Protoman Data 23 octombrie 2008 16:11:43
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>
#include <algorithm>
#define mx 510000

using namespace std;

char s[10 * mx];
pair <int, int> dq[mx];
int a[mx];
int n, k, stdq = 1, sfdq = 1, maxim, ts, tf;

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%ld %ld\n", &n, &k);
	gets(s);
	int x = 0, r = 0, sm = 1;
	for (int i = 0; i <= strlen(s); i++)
	{
		if (s[i] == '-')
			sm = -1;
		else if ('0' <= s[i] && s[i] <= '9')
			x = x * 10 + s[i] - '0';
		else
		{
			a[++r] = x * sm;
			x = 0;
			sm = 1;
		}
	}
	dq[stdq].first = LONG_MAX;
	maxim = -LONG_MAX;
	for (int i = 1; i <= n; i++)
	{
		if (dq[stdq].second <= i - k)
			stdq++;
		int vl = min(a[i], dq[stdq].first);
		if (vl > maxim && i >= k)
		{
			ts = i - k + 1;
			tf = i;
			maxim = vl;
		}
		dq[++sfdq].first = a[i];
		dq[sfdq].second = i;
		while (dq[sfdq].first < dq[sfdq - 1].first && sfdq > stdq)
		{
			swap(dq[sfdq], dq[sfdq - 1]);
			sfdq--;
		}
	}
	printf("%ld %ld %ld", ts, tf, maxim);
	fclose(stdin);
	fclose(stdout);
	return 0;
}