Cod sursa(job #2008910)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 7 august 2017 22:42:34
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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[NMAX];
  in.get();
  in.getline(s,3500001);
  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++){
    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;
}