oj.uz

Submission #882072

# Submission time Handle Problem Language Result Execution time Memory
882072 2023-12-02T14:40:11 Z skywwla Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

using namespace std ;
using ll = long long ;

struct SegTree {
   int _n ;
   struct Node {
      ll value = 0 ;
      Node() {}
      Node(ll x) {
         value = x ;
      }
   };
   Node combine(Node l, Node r) {
      if (l.value > r.value) return l ;
      return r ;
   }
   vector<Node> t ;
   SegTree(int len) {
      _n = len ;
      t.assign(len * 4 + 1, Node(0)) ;
   }
   void modify(int i, ll x, int v, int tl, int tr) {
      if (tl == tr) {
         t[v] = combine(t[v], x) ;
    } else {
         int tm = (tl + tr) >> 1 ;
         if (i <= tm)
            modify(i, x, v << 1, tl, tm) ;
         else
            modify(i, x, v << 1 | 1, tm + 1, tr) ;
         t[v] = combine(t[v * 2], t[v * 2 + 1]) ;
      }
   }
   void modify(int i, ll x) {
      modify(i, x, 1, 1, _n) ;
   }
   Node get(int l, int r, int v, int tl, int tr) {
      if (l > tr || r < tl) return Node(0) ;
      if (l <= tl && tr <= r) return t[v] ;
      int tm = (tl + tr) >> 1 ;
      Node L = get(l, r, v << 1, tl, tm) ;
      Node R = get(l ,r, v << 1 | 1, tm + 1, tr) ;
      return combine(L, R) ;
   }
   Node get(int l, int r) {
       if (l > r) return 0 ;
      return get(l, r, 1, 1, _n) ;
   }
};

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    int n , m ; cin >> n >> m ;
    vector<ll> a(n) ;
    for (ll &i : a) cin >> i ;
    vector<ll> b ;
    for (int i = 0 ; i < n ; i++) {
        ll cur = (i + 1) * m - a[i] ;
        if (cur >= 0) {
            b.push_back(cur) ;
        }
    }
    auto calc = [&](vector<ll>& v) -> int {
        vector<ll> c(v.begin(), v.end()) ;
        sort(c.begin(), c.end()) ;
        c.erase(unique(c.begin(), c.end()), c.end()) ;
        auto get = [&](int i) -> int {
            return (lower_bound(c.begin(), c.end(), i) - c.begin() + 1) ;
        };
        SegTree s(c.size() + 1) ;
        vector<ll> dp(n, 1) ;
        for (int i = 0 ; i < n ; i++) {
            dp[i] = max(dp[i], s.get(1, get(v[i])).value + 1) ;
            s.modify(get(v[i]), dp[i]) ;
        }
        return *max_element(dp.begin(), dp.end()) ;
    };
//    cout << calc(b) << "\n" ;
    cout << n - calc(b) ;
    return 0 ;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -