Submission #675470

#	Time	Username	Problem	Language	Result	Execution time	Memory
675470		cpLover22	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	71 ms	4780 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+5;
int n, m, h[N], f[N];
void upd(int u, int v) {
  for (; u <= n+1; u += u&-u)
    f[u] = max(f[u], v);
}
int get(int u) {
  int ans = 0;
  for (; u > 0; u -= u&-u)
    ans = max(ans, f[u]);
  return ans+1;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  if (fopen("Rabbit.inp", "r"))
    freopen("Rabbit.inp", "r", stdin),
    freopen("Rabbit.out", "w", stdout);
  cin >> n >> m;
  vector<int> comp;
  for (int i = 1; i <= n; ++i)
    cin >> h[i];
  for (int i = 0; i <= n; ++i)
    h[i] = h[i] - m*i, 
    comp.emplace_back(h[i]);
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  
  int res = 0;
  for (int i = n; i >= 0; --i) {
    int v = lower_bound(comp.begin(), comp.end(), h[i]) - comp.begin() + 1;
    int cur = get(v); upd(v, cur);
    if (!i) return cout << n+1-cur, 0;
  }
  return 0;

}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:31:7: warning: unused variable 'res' [-Wunused-variable]
   31 |   int res = 0;
      |       ^~~
triusis.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen("Rabbit.inp", "r", stdin),
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen("Rabbit.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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