Cod sursa(job #842357)

Utilizator Detrol2kGuianu Leon Detrol2k Data 26 decembrie 2012 18:43:05
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

FILE *fin=fopen("secventa.in","r");
FILE *fout=fopen("secventa.out","w");
	
deque<int> deq;
int v[500001], i, k, n, max_min, poz, j;
char c[10000010];

int char_to_int()
{
	int aux = 0, sign = 1;
	
	if(c[j] == '-')
	{
		sign = -1;
		j++;
	}
	while(c[j] != ' ' && c[j] != '\0')
	{
		aux = aux*10 + (c[j] - '0');
		j++;
	}
	j++;
	
	return sign * aux;
}

int main()
{
	//Read
	fscanf(fin,"%d %d",&n,&k);	
	fgetc(fin);
	fgets(c,1000010,fin);
	

	//Compute
	for(i=1; i<=k; i++)
	{
		v[i] = char_to_int();
		while(!deq.empty() && v[deq.back()] > v[i])
			deq.pop_back();
		deq.push_back(i);
	}

	max_min = v[deq.front()];
	poz = k;
	
	for(i=k+1; i<=n; i++)
	{
		v[i] = char_to_int();
		while(!deq.empty() && v[deq.back()] > v[i])
			deq.pop_back();
		deq.push_back(i);
		if(deq.front() == i-k)
			deq.pop_front();
		if(max_min < v[deq.front()])
		{
			max_min = v[deq.front()];
			poz = i;
		}
	}		


	//Print
	fprintf(fout,"%d %d %d",poz-k+1,poz,max_min);
}