Submission #890286

#	Time	Username	Problem	Language	Result	Execution time	Memory
890286		toastifishi	Rabbit Carrot (LMIO19_triusis)	C++14	0 / 100	1 ms	600 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 + 1); brr.resize(n + 1);
    for(int i = 1; i <= n; i++) cin >> arr[i];

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

    pos[0] = 0;
    for(int i = 1; i <= n; i++) pos[brr[i]] = i;

    int ans = n;
    for(int i = n; i >= 1; i--) {
        int ii = upper_bound(brr.begin() + 1, brr.end(), arr[i] + m) - brr.begin(); 
        int v = query(1, 1, n, 1, pos[brr[ii - 1]]) + 1; update(1, 1, n, pos[arr[i]], v);   
        if(arr[i] <= m * i) 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;
      |              ~~^~~

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