Submission #890287

#	Time	Username	Problem	Language	Result	Execution time	Memory
890287		toastifishi	Rabbit Carrot (LMIO19_triusis)	C++14	0 / 100	0 ms	348 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;

int n, m;
map <int, int> pos;
vector <int> arr, brr, tree;
void update(int node, int l, int r, int i, int v) {
    if(l == r) {
        tree[node] = v;
        return;
    }
    int md = l + r >> 1;
    if(i <= md) update(node * 2, l, md, i, v);
    else update(node * 2 + 1, md + 1, r, i, v); 
    tree[node] = max(tree[node * 2], tree[node * 2 + 1]); 
}
int query(int node, int l, int r, int L, int R) {
    if(r < L || l > R) return 0;
    if(L <= l && r <= R) return tree[node];

    int md = l + r >> 1;
    return max(query(node * 2, l, md, L, R), query(node * 2 + 1, md + 1, r, L, R));  
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    tree.resize(4 * n); 
    arr.resize(n); brr.resize(n);
    for(int i = 0; i < n; i++) cin >> arr[i];

    brr = arr;
    sort(brr.begin(), brr.end());
    brr.erase(unique(brr.begin(), brr.end()), brr.end());

    pos[0] = -1;
    for(int i = 0; i < brr.size(); i++) pos[brr[i]] = i;
    
    int ans = n;
    for(int i = n - 1; i >= 0; i--) {
        int ii = upper_bound(brr.begin(), brr.end(), arr[i] + m) - brr.begin();
        int v = 0;
        if(ii) { 
            v = query(1, 0, n - 1, 0, pos[brr[ii - 1]]) + 1;
            update(1, 0, n - 1, pos[arr[i]], v);   
        }
        if(arr[i] <= m * (i + 1)) ans = min(ans, n - v); 
    }   
    cout << ans << "\n"; 
    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'void update(int, int, int, int, int)':
triusis.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int md = l + r >> 1;
      |              ~~^~~
triusis.cpp: In function 'int query(int, int, int, int, int)':
triusis.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int md = l + r >> 1;
      |              ~~^~~
triusis.cpp: In function 'int main()':
triusis.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < brr.size(); i++) pos[brr[i]] = i;
      |                    ~~^~~~~~~~~~~~

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