Cod sursa(job #216301)

Utilizator ProtomanAndrei Purice Protoman Data 23 octombrie 2008 20:49:03
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#include <algorithm>
#define mx 1 << 19

using namespace std;

char s[1 << 22];
pair <short, int> dq[mx];
short 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("%d %d\n", &n, &k);
	fgets(s, 1 << 22, stdin);
	int x = 0, sm = 1, xx = strlen(s);
	for (int id = 0, i = 0; id <= xx; id++)
	{
		if (s[id] == '-')
			sm = -1;
		else if ('0' <= s[id] && s[id] <= '9')
			x = x * 10 + s[id] - '0';
		else
		{
			a[++i] = x * sm;
			x = 0;
			sm = 1;
		}
	}
	dq[stdq].first = 30001;
	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("%d %d %d", ts, tf, maxim);
	fclose(stdin);
	fclose(stdout);
	return 0;
}