제출 #1285313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285313		beka19	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	2 ms	576 KiB

triusis

    #include <bits/stdc++.h>
using namespace std;
#define sped ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define s second
#define f first
#define int long long
const int N = 1e6 + 1;
int t[N*36],L[N * 36],R[N * 36];
int z[N * 36];
int cntv = 2;
void update(int v,int tl,int tr,int pos){
   if(tl == tr){
        t[v]++;
   }
   else{
     int tm = (tl + tr) / 2;
     if(pos <= tm){
     if(L[v] == 0) L[v] = cntv++;
     update(L[v],tl,tm,pos);
     }
     else{
     if(R[v] == 0) R[v] = cntv++;
     update(R[v],tm+1,tr,pos);
     }
     t[v] = t[L[v]] + t[R[v]];
   }
}
int get(int v,int tl,int tr,int l,int r){
    if(l > r) return 0;
  if(t[v] == 0) return 0;
  if(tl > r || l > tr) return 0;
   if(tl >= l && tr <= r){
       return t[v];
   }
   int tm = (tl + tr) / 2;
   return get(L[v] ,tl,tm,l,r) + get(R[v] ,tm+1,tr,l,r);
}
void okok(){
   int n;
   cin >> n;
   int m;
   cin >> m;
   int a[n + 1];
   vector < int > v;
   vector < int > b;
   for(int i= 1;i <= n;i++){
    cin >> a[i];
    a[i] = a[i] - i * m;
     b.pb(-1 * a[i]);
   }
   v.pb(0);
   for(int to : b){
    auto it = lower_bound(v.begin(),v.end(),to) - v.begin();
    if(v.back() <= to){
        v.pb(to);
    }
    else v[it] = to;
   }
   cout << n - (v.size() - 1);
}
signed main() {
//freopen("bank.in", "r", stdin) ;
//freopen("bansk.out", "w", stdout);
sped
int tt = 1;
//cin >> tt;
while(tt--){
    okok();
    //cout << '\n';
    }
}

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