Cod sursa(job #1493633)

Utilizator cella.florescuCella Florescu cella.florescu Data 29 septembrie 2015 18:47:26
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 500000
#define LIM 4194304
int aux[200], p=LIM-1;
#define aux (aux+1)
char s[LIM];
FILE *fin;

inline void avans(){
  if(++p==LIM){
    fread(s, 1, LIM, fin);
    p=0;
  }
}

inline int getnr(){
  int semn=1, nr=0;
  while(aux[s[p]]==0)
    avans();
  if(s[p]=='-'){
    semn=-1;
    avans();
  }
  while(aux[s[p]]){
    nr=nr*10+s[p]-'0';
    avans();
  }
  return nr*semn;
}

int deque[MAXN], v[MAXN];

int main()
{
    FILE *fout;
    int n, k, i, b, e, max, pos;
    for(i='0'; i<='9'; i++)
      aux[i]=1;
    aux['-']=1;
    fin=fopen("secventa.in", "r");
    fscanf(fin, "%d%d", &n, &k);
    for(i=0; i<n; i++)
      v[i]=getnr();
    fclose(fin);
    b=e=0; max=-2000000000;
    for(i=0; i<n; i++){
      if(deque[b]==i-k)
        ++b;
      while(e>b && v[deque[e-1]]>v[i])
        --e;
      deque[e++]=i;
      if(i>=k-1 && v[deque[b]]>max){
        max=v[deque[b]];
        pos=i-k+1;
      }
    }
    fout=fopen("secventa.out", "w");
    fprintf(fout, "%d %d %d\n", pos+1, pos+k, max);
    fclose(fout);
    return 0;
}