Cod sursa(job #999983)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 21 septembrie 2013 19:35:50
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>
#include <deque>
#define dim 500005
#define DIM 5000000
#define push push_back
using namespace std;

int main()
{
    int N,K,i,j,aux,in,MIN = -35000;
    int 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++;
    }
    fclose(f);

    for(i = 1; i <= N; ++i)
    {
       // fscanf(f,"%d",&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){
            in = i-K+1;
            MIN = v[Q.front()];
        }
    }
    fprintf(g,"%d %d %d\n",in,in+K-1,MIN);

fclose(g);
return 0;
}