Submission #1132002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132002		NoMercy	Financial Report (JOI21_financial)	C++20	100 / 100	426 ms	26268 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Segtree {
    #define left v + 1
    #define right v + 2 * (tm - tl)
    struct pi {
        ll mx = 0;
    } emp;
    vector<pi> tree;
    void init (int x) {
        tree.assign (x << 1, emp);
    }

    void update (int v, int tl, int tr, int pos, ll val) {
        if (tl + 1 == tr) {
            tree[v].mx = val;
            return;
        } 
        int tm = (tl + tr) >> 1;
        if (pos < tm) update (left, tl, tm, pos, val);
        else update (right, tm, tr, pos, val);
        tree[v].mx = max(tree[left].mx, tree[right].mx);
    }
    ll get (int v, int tl, int tr, int ql, int qr) {
        if (tl >= qr || ql >= tr) {
            return 0LL;
        }
        if (ql <= tl && tr <= qr) {
            return tree[v].mx;
        }
        int tm = (tl + tr) >> 1;
        return max (get (left, tl, tm, ql, qr), get (right, tm, tr, ql, qr));
    }
};

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, D;
    cin >> N >> D;
    vector<ll> arr(N);
    vector<array<ll, 2>> events;
    for (int i = 0;i < N;i ++) {
        cin >> arr[i];
        events.push_back({arr[i], -i});
    }
    sort (events.begin(), events.end());
    
    Segtree ST;
    ST.init (N + 2);
    set<ll> index, alive;
    for (auto [val, ind] : events) {
        ind = -ind;
        auto it = index.upper_bound(ind);
        if (it == index.begin() || *prev(it) + D < ind) {
            alive.insert(ind);
        }
        index.insert(ind);

        it = alive.upper_bound(ind);
        if (it != alive.end() && *it <= ind + D) {
            it = alive.erase(it);
        }
        ST.update (0, 0, N, ind, 1 + ST.get (0, 0, N, *prev (it), ind + 1));
    }
    cout << ST.get (0, 0, N, 0, N) << '\n';
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35