Cod sursa(job #1144764)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 17 martie 2014 15:59:58
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");

const int nmax = 500005;
int d[nmax], p = 1, q = 0, maxim = -1000000, bestbeg, bestend, n, k, v[nmax], nr, len, act, l = 1;
bool semn;
char ca[10 * nmax];

int main(){
	int player_unu=0;

	in>>n>>k;
	in.get();
	in.get(ca, 10*nmax);
	len = strlen(ca);
	for(int i = 0; i<len; i++)
	{
		if('0'<=ca[i] && ca[i]<='9')
		{
			act = act * 10 + ca[i] - '0';
		}
		if(ca[i]=='-')
			semn = 1;
		if(ca[i]==' ')
		{
			if(semn==1)
				act = -act;

			v[l] = act;
			l++;

			semn = act = 0;
		}
	}
	if(l!=n+1)
	{
		if(semn==1)
				act = -act;

			v[l] = act;
			l++;

			semn = act = 0;
	}

	for(int i = 1; i<=n; i++)
	{

		while(v[d[q]]>v[i] && p<=q)
			q--;

		q++;
		d[q] = i;

		while (i-nr>k) {
            nr++;
            if (nr==d[p])
                p++;
        }
        if (i-nr==k) {
            if (maxim < v[d[p]]) {
                maxim=v[d[p]];
                bestbeg=nr+1;
                bestend=i;
            }
        }
	}

	out<<bestbeg<<" "<<bestend<<" "<<maxim<<'\n';
	return player_unu;
}