Submission #1218751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218751		thewizardman	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	3 ms	2888 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], b[200001], dp[200001], st[400001];
map<int, int> compress;

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

int query(int l, int r) {
  int ret = ninf;
  for (l += n+1, r += n+1; 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 main() {
  bruh;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) b[i] = a[i];
  sort(b+1, b+n+1);
  compress[0] = 0;
  for (int i = 1; i <= n; i++) compress[b[i]] = i;

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

  for (int i = 1; i <= n; i++) {
    auto ub = compress.lower_bound(a[i]-m);
    dp[i] = ub == compress.end() ? ninf : (query(ub->second, n) + 1);
    // cout << ub->second << ' ' << compress[a[i]] << ' ' << dp[i] << '\n';
    update(compress[a[i]], dp[i]);
  }
  for (int i = 1; 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