Submission #1218801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218801		thewizardman	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	3 ms	2700 KiB

triusis

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define plpll pair<ll, pll>
#define pipii pair<int, pii>
#define plpii pair<ll, pii>
#define pipll pair<int, pll>
#define lll tuple<ll, ll, ll>
#define iii tuple<int, int, int>
#define lii tuple<ll, int, int>
#define lli tuple<ll, ll, int>
#define md 1000000007LL
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define lninf 0xc0c0c0c0c0c0c0c0
#define ninf 0xc0c0c0c0
#define bruh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n, m, ans, a[200001], dp[200001], st[400001];
vector<int> b;

void update(int i, int val) {
  for (i += n; i > 0; i >>= 1) st[i] = max(st[i], val);
}

int query(int l, int r) {
  int ret = ninf;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) ret = max(ret, st[l++]);
    if (r & 1) ret = max(ret, st[--r]);
  }
  return ret;
}

int compress(int i) {
  return lower_bound(b.begin(), b.end(), i) - b.begin();
}

int main() {
  bruh;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  b.resize(n);
  for (int i = 0; i < n; i++) b[i] = a[i];
  sort(b.begin(), b.end());
  b.erase(unique(b.begin(), b.end()), b.end());

  memset(st, 0xc0, sizeof st);
  memset(dp, 0xc0, sizeof dp);

  for (int i = 0; i < n; i++) {
    if (a[i] <= m) dp[i] = 1;
    dp[i] = max(dp[i], query(compress(a[i]-m), n) + 1);
    update(compress(a[i]), dp[i]);
  }
  for (int i = 0; i < n; i++) ans = max(ans, dp[i]);
  cout << n - ans;
}

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