Cod sursa(job #2153761)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 6 martie 2018 13:58:08
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int MAXK = 5e5;
const int MAXN = 5e5;

struct numar{
  int val;
  int poz;

  numar (int _a = 0, int _b = 0){
    val = _a;
    poz = _b;
  }
};

deque <numar>minime;

int maxMin = -30000;
int n, k;
int startPoz;
int v[MAXN + 1];

int main(){
  in >> n >> k;

  for (int i = 1; i < k; ++ i){
    numar nr;
    in >> nr.val;
    nr.poz = i;
    v[i] = nr.val;

    if (minime.size())
      while (minime.back().val >= nr.val){
        minime.pop_back();
        if (minime.empty())
          break;
      }

    minime.push_back(nr);

  }

  for (int i = k; i <= n; ++ i){
    numar nr;
    in >> nr.val;
    nr.poz = i;
    v[i] = nr.val;

    if (minime.size())
      if (minime.front().poz < i - k + 1)
        minime.pop_front();

    if (minime.size())
      while (minime.back().val >= nr.val){
        minime.pop_back();
        if (minime.empty())
          break;
      }
    minime.push_back(nr);

    if (maxMin < minime.front().val){
      maxMin = minime.front().val;
      startPoz = i - k + 1;
    }

  }

  for (int i = startPoz; i < startPoz + k; ++ i)
    out << v[i] << " ";


  return 0;
}