Submission #747661

#	Time	Username	Problem	Language	Result	Execution time	Memory
747661		vjudge1	Rabbit Carrot (LMIO19_triusis)	C++14	0 / 100	1 ms	340 KiB

triusis

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;

#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define pb push_back

const int N = 2e5 + 5;

int n, a[N], m;
int fw[N];
ll b[N];

void update(int x, int y) {
  for (; x; x -= x & -x) fw[x] = max(fw[x], y);
}

int get(int x) {
  int ans = 0;
  for (; x <= n; x += x & -x) ans = max(ans, fw[x]);
  return ans;
}

int lis() {
  vector<pair<ll, int>> c(n);
  for (int i = 1; i <= n; ++i) c[i - 1] = {b[i], i};

  sort(all(c));
  int nxt = 1;
  for (int i = 0; i < n; ++i) {
    if (i > 0 && c[i].first != c[i - 1].first) nxt += 1;
    b[c[i].second] = nxt;
  }

  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    int x = get(b[i]) + 1;
    update(b[i], x);
    ans = max(ans, x);
  }
  return ans;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    b[i] = a[i] - 1LL * i * m;
  }

  cout << n - lis();
}

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