Cod sursa(job #1577601)

Utilizator herbertoHerbert Mohanu herberto Data 23 ianuarie 2016 16:31:30
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#include<deque>
#define MAXN 500001
#define MINK -30001
using namespace std;

deque <int> d;
deque <int> poz;
int v[MAXN];
int main(){
  FILE*fin=fopen("secventa.in", "r");
  FILE*fout=fopen("secventa.out", "w");
  int n, k, i, max, a, ret, nr, semn;
  char c;
  fscanf(fin, "%d%d", &n, &k);
  i=1;
  nr=0;
  semn=1;
  fgetc(fin);
  c=fgetc(fin);
  while(c!='\n' && c!=EOF){
    if(c=='-')
      semn=-1;
    else{
      if(c>='0' && c<='9')
        nr=nr*10+c-'0';
      else{
        nr*=semn;
        v[i]=nr;
        i++;
        nr=0;
        semn=1;
      }
    }
    c=fgetc(fin);
  }
  v[i]=semn*nr;
  max=MINK;
  for(i=1; i<=n; i++){
    if(!d.empty() && i-poz.front()>=k){
      d.pop_front();
      poz.pop_front();
    }
    a=v[i];
    while(!d.empty() && a<=d.back()){
      d.pop_back();
      poz.pop_back();
    }
    d.push_back(a);
    poz.push_back(i);
    if(d.front()>max && i>=k){
      max=d.front();
      ret=i;
    }
  }
  fprintf(fout, "%d %d %d", ret-k+1, ret, max);
  return 0;
}