Submission #1128978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128978		micro7	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	115 ms	4680 KiB

triusis

#include <algorithm>
#include <cstdio>
#include <functional>
#include <limits>
using namespace std;

constexpr int MAXN = 2e5;
int n, m, a[MAXN + 1];

int dp[MAXN + 1];

int vals[MAXN + 1];

int tr[4 * MAXN + 1];
void build(int p, int l, int r) {
  if (l == r) {
    tr[p] = numeric_limits<int>::min();
    return;
  }
  int mid = (l + r) / 2;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
  tr[p] = max(tr[p * 2], tr[p * 2 + 1]);
}
int query(int s, int t, int p, int l, int r) {
  if (s <= l && r <= t) {
    return tr[p];
  }
  int mid = (l + r) / 2;
  int ret = numeric_limits<int>::min();
  if (s <= mid) {
    ret = max(ret, query(s, t, p * 2, l, mid));
  }
  if (t > mid) {
    ret = max(ret, query(s, t, p * 2 + 1, mid + 1, r));
  }
  return ret;
}
void update(int i, int x, int p, int l, int r) {
  if (l == r) {
    tr[p] = x;
    return;
  }
  int mid = (l + r) / 2;
  if (i <= mid) {
    update(i, x, p * 2, l, mid);
  } else {
    update(i, x, p * 2 + 1, mid + 1, r);
  }
  tr[p] = max(tr[p * 2], tr[p * 2 + 1]);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    vals[i] = a[i] - i * m;
  }

  sort(vals, vals + n + 1, greater<>());
  int p = unique(vals, vals + n + 1) - vals;
  build(1, 0, p - 1);
  update(lower_bound(vals, vals + p, 0, greater<>()) - vals, 0, 1, 0, p - 1);
  for (int i = 1; i <= n; ++i) {
    dp[i] = numeric_limits<int>::min();
    int k = upper_bound(vals, vals + p, a[i] - i * m, greater<>()) - vals;
    dp[i] = query(0, k - 1, 1, 0, p - 1) + 1;
    update(k - 1, dp[i], 1, 0, p - 1);
  }
  printf("%d", n - *max_element(dp, dp + n + 1));

  return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
triusis.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37