Cod sursa(job #2008915)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 7 august 2017 22:49:41
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <string.h>
#define NMAX 500001
#define VMIN LLONG_MIN

using namespace std;

ifstream in ("secventa.in");
ofstream out("secventa.out");

int n, k, v[NMAX];//date de intrare
int coada[NMAX], st, dr;
long long valMAx;
int stMax, drMAx;

void citire(){
  in >> n >> k;
  char s[1500001];
  in.get();
  in.getline(s, 1500001);
  int nr = 1, lg;
  bool semn;
  lg = strlen(s);
  for(int i = 0; i < lg; i++){
   semn = true;
   if(s[i] == '-'){
      semn = false;
      i++;
    }
   while(s[i] >= '0' && s[i] <= '9'){
    v[nr] = v[nr] * 10 + (s[i] - '0');
    i++;
   }
   if(semn == false){
    v[nr] = -v[nr];
   }
   nr++;
  }
}

void rezolvare(){
  long long valMAx = LLONG_MIN;
  st = 1;
  dr = 0;
  for(int i = 1; i <= n; i++){
    in >> v[i];
    while(v[coada[dr]] > v[i] && dr >= st){
      dr --;
    }
    coada[++dr] = i;
    if((i - k) == coada[st]){
      st ++;
    }
    if(i >= k && v[coada[st]] > valMAx){
      valMAx = v[coada[st]];
      stMax = i - k + 1;
      drMAx = i;
    }
  }
  out << stMax << ' ' << drMAx << ' ' << valMAx ;
}

int main(){
  citire();
  rezolvare();
  return 0;
}