Cod sursa(job #969819)

Utilizator bugyBogdan Vlad bugy Data 5 iulie 2013 13:52:50
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <deque>
#define dim 500005
#define DIM 3000000
#define push push_back
using namespace std;
 
int main()
{
    int N,K,i,j,aux,in,sf,MIN = -(1<<30);
    short v[dim];
    deque<int> Q;
	char sir[DIM];
     
    FILE *f=fopen("secventa.in","r"), *g=fopen("secventa.out","w");
     
    fscanf(f,"%d %d\n",&N,&K);
	
	fgets(sir,DIM,f);
	i=0;j=1;
	aux=0;
	while(sir[i] != '\n')
	{
		while(sir[i]==' ') i++;      
		if(sir[i]=='-') {aux=1;i++;}
		while(sir[i]>='0' &&sir[i]<='9') {v[j]=v[j]*10+sir[i]-'0';i++;}
		if(aux) v[j]=-v[j],aux=0;
		j++;
	}


    for(i = 1; i <= N; i++)
    {
       // fscanf(f,"%hd",&v[i]);
 
        while(!Q.empty() && Q.front() < i - K + 1)
            Q.pop_front();
        while(!Q.empty() && v[Q.back()] >= v[i])
            Q.pop_back();
         
        Q.push(i);
  
        if(v[Q.front()] > MIN && i >= K){
            sf = i;
			in = i-K+1;
            MIN = v[Q.front()];
        }
    }
    fprintf(g,"%d %d %d\n",in,sf,MIN);
return 0;
}