Cod sursa(job #809573)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 8 noiembrie 2012 18:06:26
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <cstring>
using namespace std;
#define SIZE 5000001

int deq[SIZE];
int vect[SIZE];
char strg[SIZE * 15];

int get(int &st,int dr)
{
	int minus = 0;
	int nr = 0;
	if (strg[st] == '-')
	{
		minus = 1;
		st++;
	}
	while ('0' <= strg[st] && strg[st] <= '9' && st < dr)
	{
		nr = nr*10 + (strg[st] - '0');
		st++;
	}
	st++;
	if (minus == 0) return nr;
	else return -nr;

}

int main(int argc,char *argv[])
{

	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	int n;
	int k;
	int minim = -500001;
	scanf("%d%d\n",&n,&k);
	gets(strg);
	int st = 0;
	int fin = strlen (strg);


	int poz;
	int start = 0;
    int end = -1;
	for (int i=0;i<n;i++)
    {
        vect[i] = get(st,fin);
        while (end >= start && vect[i] <= vect[deq[end]])
        {
            end--;
        }
        end++;
        deq[end] = i;
		while (deq[end] - deq[start] >= k) start++;

		if (minim < vect[deq[start]] && i +1 >= k)
		{
			minim = vect[deq[start]];
			poz = i;
		}

    }
	printf("%d %d %d",poz-k+2,poz +1,minim);
		return 0;
}