Cod sursa(job #2496002)

Utilizator lucametehauDart Monkey lucametehau Data 20 noiembrie 2019 09:05:04
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>

using namespace std;

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

int n, k;
int vf, mx, ansl, ansr;

int v[500005], l[500005], st[500005];

int main() {
  cin >> n >> k;
  for(int i = 1; i <= n; i++) {
    cin >> v[i];
    while(vf && v[st[vf]] > v[i])
      vf--;
    l[i] = st[vf] + 1;
    st[++vf] = i;
  }
  vf = 0, st[vf] = n + 1;
  mx = -30005;
  for(int i = n; i >= 1; i--) {
    while(vf && v[st[vf]] >= v[i])
      vf--;
    // intre l[i] si st[vf] - 1
    if(st[vf] - l[i] < k)
      st[++vf] = i;
    else {
      if(v[i] > mx) {
        mx = v[i];
        ansl = max(i - k + 1, l[i]), ansr = max(i - k + 1, l[i]) + k - 1;
      }
      st[++vf] = i;
    }
  }
  cout << ansl << " " << ansr << " " << mx;
  return 0;
}