Submission #1128661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128661		VinhLuu	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	80 ms	6588 KiB

triusis

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

#define lpv

#ifndef lpv
#include "AC.h"
#endif // lpv

#define int long long

const int N = 2e5 + 5;
const int oo = -1e9;

int n, m, a[N], st[N << 1];
vector<int> rrh;
int sz;

void update(int i,int val) {
  i += sz - 1;
  st[i] = max(st[i], val);
  while(i > 1) {
    i /= 2;
    st[i] = max(st[i], val);
  }
}
int get(int l,int r) {
  if(l > r) return oo;
  r++;
  int ret = oo;
  for(l += sz - 1, r += sz - 1; l < r; l /= 2, r /= 2) {
    if(l & 1) ret = max(ret, st[l ++]);
    if(r & 1) ret = max(ret, st[-- r]);
  }
  return ret;
}

#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> m;
  rrh.push_back(0 - 0 * m);
  for(int i = 1; i <= n; i ++) {
    cin >> a[i];
    rrh.push_back(a[i] - i * m);

  }

  sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());

  sz = (int)rrh.size();

  for(int i = 1; i <= 2 * sz; i ++) st[i] = oo;

  int ans = 0;

  int pos = lower_bound(all(rrh), 0) - rrh.begin() + 1;
  update(pos, 0);

  for(int i = 1; i <= n; i ++) {
    pos = lower_bound(all(rrh), a[i] - i * m) - rrh.begin() + 1;
    int val = get(pos, sz) + 1;
//    cerr << i << " " << a[i] - i * m << " " << pos << " " << val << " t\n";
    update(pos, val);
    ans = max(ans, val);
  }
  cout << n - ans;

}

#endif // lpv

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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