Cod sursa(job #969774)

Utilizator bugyBogdan Vlad bugy Data 5 iulie 2013 12:54:35
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>
#include <deque>
#define dim 500005
#define push push_back
using namespace std;

int main()
{
	int N,K,i,in,sf,MIN = -(1<<30);
	short v[dim];
	deque<int> Q;
	
	FILE *f=fopen("secventa.in","r"), *g=fopen("secventa.out","w");
	
	fscanf(f,"%d %d",&N,&K);
	
	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;
}