Cod sursa(job #1602134)

Utilizator krityxAdrian Buzea krityx Data 16 februarie 2016 16:21:17
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <deque>
#include <fstream>
#include <sstream>
#define NMAX 5001
using namespace std;

void read(char *&p, int &val)
{
	val = 0;
	bool sign = false;
	while (*p == ' ' || *p == '\n')
	{
		p++;
	}
	if (*p == '-')
	{
		sign = true;
		p++;
	}
	while (*p >= '0' && *p <= '9')
	{
		val = val * 10 + (*p - '0');
		p++;
	}

	if (sign)
	{
		val *= -1;
	}
}

int main()
{
	char *s = new char[10 * 1024 * 1024];
	int n, k, v[NMAX], i, baza, end, max = - (1<<30);
	deque<int> dq;
	ifstream fin("secventa.in");
	fin.read(s, 10 * 1024 * 1024);
	size_t bytesRead = fin.gcount();
	s[bytesRead] = '\0';

	char *p = s;
	char *pend = p + bytesRead;

	read(p, n);
	read(p, k);


	for (i = 1; i <= n; i++)
	{
		read(p, 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;
			}
		}
	}
	ofstream g("secventa.out");
	g << end - k + 1 << " " << end << " " << max;
	g.close();
	return 0;
}