Cod sursa(job #1449490)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 9 iunie 2015 19:53:37
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 500000
#define MAXNR 30000
int deque[MAXN],v[MAXN],poz[MAXN];
int main(){
    FILE*fi,*fout;
    int n,k,i,nr,b,e,max,p2;
    fi=fopen("secventa.in" ,"r");
    fout=fopen("secventa.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&k);
    for(i=0;i<n;i++)
       fscanf(fi,"%d" ,&v[i]);
    nr=-1;
    max=-MAXNR;
    for(i=0;i<k;i++){
        while(nr>=0&&deque[nr]>=v[i])
            nr--;
        nr++;
        deque[nr]=v[i];
        poz[nr]=i;
    }
    if(deque[0]>max){
        max=deque[0];
        p2=k;
    }
    b=0;
    e=nr;
    for(i=k;i<n;i++){
        if(i-k+1>poz[b])
           b++;
        while(e>=b&&deque[e]>=v[i])
           e--;
        e++;
        deque[e]=v[i];
        poz[e]=i;
        if(deque[b]>max){
           max=deque[b];
           p2=i+1;
        }
    }
    fprintf(fout,"%d %d %d" ,p2-k+1,p2,max);
    fclose(fi);
    fclose(fout);
    return 0;
}