Submission #1122505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122505		anarch_y	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	9 ms	4936 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

template<class T> struct SegmentTree{
    T def = 0;
    vector<T> tree;
    int len;

    SegmentTree(int N){
        int p = ceil(log2(N));
        len = (1<<p);
        tree.resize(2*len, def);
    }

    T f(T a, T b){
        return max(a, b);
    }

    void build(int k, int x, int y){
        if(x == y) return;
        int d = (x+y)/2;
        build(2*k, x, d);
        build(2*k+1, d+1, y);
        tree[k] = f(tree[2*k], tree[2*k+1]);
    }

    void begin(){
        build(1, 0, len-1);
    }

    void set(int id, T val, int k, int x, int y){
        if(id < x or id > y) return;
        if(x == y and x == id){
            tree[x+len] = max(tree[x+len], val); 
            return;
        }
        int d = (x+y)/2;
        if(id <= d) set(id, val, 2*k, x, d);
        else set(id, val, 2*k+1, d+1, y);
        tree[k] = f(tree[2*k], tree[2*k+1]);
    }

    void set(int id, T val){
        set(id, val, 1, 0, len-1);
    }

    T query(int a, int b, int k, int x, int y){
        if(b < x or a > y) return def;
        if(a <= x and y <= b) return tree[k];
        int d = (x+y)/2;
        T s1 = query(a, b, 2*k, x, d);
        T s2 = query(a, b, 2*k+1, d+1, y);
        return f(s1, s2);
    }

    T query(int a, int b){
        return query(a, b, 1, 0, len-1);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    vector<int> a(n+1);
    map<int, int> mp;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        mp[a[i]]++; 
        mp[a[i]+m]++;
    }
    mp[0]++; mp[m]++;
    int c = 0;
    for(auto [x, _]: mp){
        mp[x] = c++;
    }
    reverse(all(a));
    int dp[n+1] = {};
    SegmentTree<int> seg(400001);
    seg.begin();
    for(int i=0; i<=n; i++){
        int x = mp[a[i]+m];
        int mx = seg.query(0, x);
        dp[i] = mx+1;
        seg.set(mp[a[i]], dp[i]);
    }
    int ans = (n+1) - dp[n];
    cout << ans;
}

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