Cod sursa(job #1491399)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 25 septembrie 2015 10:57:33
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 500000
#define MAXNR 30000
int deque[MAXN],v[MAXN],poz[MAXN];
int lSize,conb=0;
char *buffer;
inline int cit(){
    int nr=0;
    char a;
    a=buffer[conb];
    if(a=='-')
        conb++;
    while(conb<lSize&&buffer[conb]>='0'&&buffer[conb]<='9'){
        nr=nr*10+buffer[conb]-'0';
        conb++;
    }
    if(a=='-')
         nr=-nr;
    return nr;
}
inline void blanc(){
    while(conb<lSize&&(buffer[conb]<'0'||buffer[conb]>'9')&&buffer[conb]!='-')
         conb++;
}
int main(){
    FILE*fi,*fout;
    int n,k,i,nr,b,e,max,p2;
    fi=fopen("secventa.in" ,"rb");
    fout=fopen("secventa.out" ,"w");
    fseek(fi,0,SEEK_END);
    lSize=ftell(fi);
    rewind(fi);
    buffer=(char*) malloc(sizeof(char)*lSize);
    fread(buffer,1,lSize,fi);
    n=cit();
    blanc();
    k=cit();
    blanc();
    for(i=0;i<n;i++){
        v[i]=cit();
        blanc();
    }
    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;
}