Cod sursa(job #2330659)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 28 ianuarie 2019 18:42:43
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen (".in", "r", stdin);
#endif

  freopen ("secventa.in", "r", stdin);
  freopen ("secventa.out", "w", stdout);

  int n, k;
  scanf ("%d%d", &n, &k);
  vi v (n + 2, 0);
  for (int i = 1; i <= n; ++i) {
    scanf ("%d", &v[i]);
  }

  deque <int> dq;
  int ans_max = -(1 << 30), start = -1, finish = -1;
  for (int i = 1; i <= n; ++i) {
    while (!dq.empty() && v[dq.back()] >= v[i]) {
      dq.pop_back();
    }
    dq.pb (i);
    while (dq.front() + k <= i) {
      dq.pop_front();
    }

    if (i >= k) {
      if (ans_max < v[dq.front()]) {
        ans_max = v[dq.front()];
        start = i - k + 1;
        finish = i;
      }
    }
  }

  printf ("%d %d %d\n", start, finish, ans_max);

  fclose (stdin);
  fclose (stdout);

#ifdef LOCAL_DEFINE
  fprintf (stderr, "Time elapsed: %lf s.\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}