Cod sursa(job #2330662)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 28 ianuarie 2019 18:52:35
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 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;

struct Read {
  string s;
  ifstream f;
  Read (const string &file) {
    f.open (file);
  }

  int pos = (1 << 30);
  int nextInt() {
    if (pos >= s.size()) {
      getline (f, s);
      pos = 0;
    }
    int ret = 0, sign = 1;
    if (s[pos] == '-') sign = -1, ++pos;
    while (pos < s.size() && isdigit (s[pos])) {
      (ret *= 10) += s[pos++] - '0';
    }
    ++pos;
    return ret * sign;
  }
};

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

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

  int n = in.nextInt();
  int k = in.nextInt();
  vi v (n + 2, 0);
  for (int i = 1; i <= n; ++i) {
    v[i] = in.nextInt();
  }

  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;
}