Submission #1128651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128651		ntdaccode	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	144 ms	11496 KiB

triusis

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;

const int M = 1e6 + 10;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;

int n, m, f[M], a[M];
int t[4 * M];
void upd(int s,int l,int r,int pos,int val)
{
  if(l > pos || r < pos) return ;
  if(l == r) {
    t[s] = max(t[s], val);
    return ;
  }
  int mid = (l + r)/2;
  upd(s * 2, l, mid, pos, val);
  upd(s * 2 + 1, mid + 1, r, pos, val);
  t[s] = max(t[s * 2], t[s * 2  + 1]);
}

int get(int s,int l,int r,int u,int v)
{
  if(l > v || r < u) return -1e9;
  if(u <= l && r <= v) return t[s];
  int mid = (l + r)/2;
  return max(get(s * 2, l, mid, u, v), get(s * 2 + 1, mid + 1, r, u, v));
}
vector<int> rrh;
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  if(fopen("1.inp","r")) {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }

  #define task ""
  if(fopen(task".inp","r")) {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n >> m;
  for(int i = 1;i <= n; i++) {
      cin >> a[i];
      rrh.pb(i * m - a[i]);
  }
  rrh.pb(0);
  sort(rrh.begin(), rrh.end());
  //for(int v : rrh) cout << v << " ";
  for(int i = 0;i <= 4 * n; i++) t[i] = -1e9;
  int idx = lower_bound(rrh.begin(), rrh.end(), 0) - rrh.begin();
  //cout << idx << " ";
  upd(1, 0, n, idx, 0);
  for(int i = 1; i<= n; i++) {
      idx = lower_bound(rrh.begin(),rrh.end(),i * m - a[i]) - rrh.begin();
      //if(idx == -1) continue;
      //cout << idx << " ";
      f[i] = get(1, 0, n, 0, idx) + 1;
     //cout << f[i] << " ";

      upd(1, 0, n, idx, f[i]);
  }
  int kq = n;
  for(int i = 1;i <= n; i++) {
      kq = min(kq, n - f[i]);
  }
  cout << kq;


}

Compilation message (stderr)

triusis.cpp: In function 'int32_t main()':
triusis.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
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("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
triusis.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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