Cod sursa(job #809397)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 8 noiembrie 2012 11:32:20
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>
#include <iostream>
#include <cstdlib>

using namespace std;
#define SIZE 5000001

int deq[SIZE];
int vect[SIZE];

int main(int argc,char *argv[])
{
	FILE *input = fopen("secventa.in","r");
	FILE *output = fopen("secventa.out","w");
	int n;
	int k;
	int minim = -500001;
	fscanf(input,"%d%d",&n,&k);
	for (int i=0;i<n;i++)
	{
		fscanf(input,"%d",&vect[i]);
	}
	int poz;
	int start = 0;
    int end = -1;
	for (int i=0;i<n;i++)
    {		
        while (end >= start && vect[i] <= vect[deq[end]])
        {
            end--;
        }
        end++;
        deq[end] = i;
		while (deq[end] - deq[start] >= k) start++;
		
		if (minim < deq[start] && i +1 >= k)
		{
			minim = vect[deq[start]];
			poz = i;
		}			

    }
	fprintf(output,"%d %d %d",poz-k+1+1,poz+1,minim);
	fclose(input);
	fclose(output);
	return 0;
}