Cod sursa(job #1602114)

Utilizator krityxAdrian Buzea krityx Data 16 februarie 2016 15:54:18
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <deque>
#include <string>
#include <fstream>
#include <sstream>
#define NMAX 500001
using namespace std;

int main()
{
	int n, k, v[NMAX], i, baza, start, end, max = - (1<<30);
	deque<int> dq;
	ifstream fin("secventa.in");
	stringstream bfr;
	bfr << fin.rdbuf();
	//string test = bfr.str();
	//read(bfr, n);
	//FILE *f = fopen("secventa.in", "r");
	////fscanf(f, "%s", &s);
	//fscanf(f, "%d %d", &n, &k);
	bfr >> n >> k;
	for (i = 1; i <= n; i++)
	{
		//fscanf(f, "%d", &v[i]);
		bfr >> v[i];
	}
	dq.push_back(1);
	for (i = 2; i <= n; i++)
	{
		while (!dq.empty() && dq.front() < i - k + 1)
		{
			dq.pop_front();
		}
		while (!dq.empty() && v[dq.back()] > v[i])
		{
			dq.pop_back();
		}
		dq.push_back(i);
		if (i >= k)
		{
			baza = dq.front();
			if (v[baza] > max)
			{
				max = v[baza];
				end = i;
			}
		}
	}
	FILE *g = fopen("secventa.out", "r");
	fprintf(g, "%d %d %d", end - k + 1, end, max);
	return 0;
}