Cod sursa(job #2533792)

Utilizator anabatAna Batrineanu anabat Data 29 ianuarie 2020 18:33:28
Problema Secventa Scor 70
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 500000

int v[NMAX+1],deque[NMAX+1];
int inceput, sfarsit;

void pop_front(){
  inceput++;
}
void pop_back(){
  sfarsit--;
}
void push_back(int x){
  deque[sfarsit]=x;
  sfarsit++;
}
char empty(){
  return(inceput>=sfarsit);
}

int main()
{
  FILE *fin,*fout;
  fin=fopen("secventa.in","r");
  fout=fopen("secventa.out","w");

  int i,n,k,max,secvleft,secvright,j;
  fscanf(fin,"%d%d",&n,&k);
  for(i=1;i<=n;i++){
    fscanf(fin,"%d",&v[i]);
  }
  max=-30001;
  secvleft=0;
  secvright=0;
  for(i=1;i<=n;i++){
    if(i>k){
      if(v[deque[inceput]]>max){
        max=v[deque[inceput]]; ///memorez baza maxima
        secvleft=i-k; ///poz de unde incepe secventa
        secvright=i-1;///poz unde se termina secventa
      }
    }
    if(deque[inceput]<=i-k){ ///elimin baza deoarece incepe o noua secv
      pop_front();
    }
    while(!empty()&&v[i]<v[deque[sfarsit-1]]&&i!=1){ ///daca nr nou < decat sfarsitul
      pop_back();
    }
    push_back(i);
  }
  if(v[deque[inceput]]>max){
    max=v[deque[inceput]]; ///memorez baza maxima
    secvleft=i-k; ///poz de unde incepe secventa
    secvright=i-1;///poz unde se termina secventa
  }

  fprintf(fout,"%d %d %d", secvleft, secvright, max);

  fclose(fin);
  fclose(fout);
  return 0;
}