Cod sursa(job #911274)

Utilizator fhandreiAndrei Hareza fhandrei Data 11 martie 2013 14:45:28
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
// Include
#include <fstream>
#include <cstdio>
#include <deque>
using namespace std;

// Definitii
#define mp make_pair
#define pb push_back
#define popb pop_back
#define popf pop_front

#define pii pair<int, int>
#define val first
#define id second

// Constante
const int oo = (1<<30)-1;
const int parseSZ = (int)35e2+5;

// Functii
int mustADD(int x);

// Variabile
ifstream in("secventa.in");
ofstream out("secventa.out");

char parseSTR[parseSZ], *parse=parseSTR;

int num, len;

deque<pii> values;
pii maxVal = mp(-oo, -oo);

// Main
int main()
{
	in >> num >> len;
	in.get();
	in.getline(parse, parseSZ);
	for(int i=1 ; i<len ; ++i)
	{
		int readVal;
		sscanf(parse, "%d", &readVal);
		parse += (1+mustADD(readVal));
		while(!values.empty() && readVal < values.back().val)
			values.popb();
		values.pb(mp(readVal, i));
	}
	
	for(int i=len ; i<=num ; ++i)
	{
		int readVal;
		sscanf(parse, "%d", &readVal);
		parse += (1+mustADD(readVal));
		while(!values.empty() && readVal < values.back().val)
			values.popb();
		values.pb(mp(readVal, i));
		
		if(i - values.front().id == len)
			values.popf();
		
		if(maxVal.val < values.front().val)
		{
			maxVal.val = values.front().val;
			maxVal.id = i;
		}
	}
	
	out << maxVal.id-len+1 << ' ' << maxVal.id << ' ' << maxVal.val << '\n';
	
	
	in.close();
	out.close();
	return 0;
}

int mustADD(int x)
{
	int answer = 0;
	if(x < 0)
		x = -x, ++answer;
	while(x)
		++answer, x/=10;
	return answer;
}