Submission #1035119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035119		CommandMaster	Financial Report (JOI21_financial)	C++17	100 / 100	337 ms	30600 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>

struct SEG {
    ll sz;
    vll arr;

    void make(ll n) {
        for (sz = 1; sz < n; sz <<= 1);
        arr.resize(sz*2);
    }

    void set(ll ind, ll val) {
        ind += sz;
        arr[ind] = val;
        while(ind>>=1) arr[ind] = max(arr[ind*2], arr[ind*2+1]);
    }

    ll query(ll l, ll r) {
        l += sz, r += sz;
        ll ans = 0;
        while (l <= r) {
            if (l % 2 == 1) ans = max(ans, arr[l++]);
            if (r % 2 == 0) ans = max(ans, arr[r--]);
            l>>=1, r>>=1;
        }
        return ans;
    }
};

int main() {
    ll n, d;
    cin >> n >> d;
    vector<pll> events;
    for (int i = 0; i < n; i++) {
        ll v;
        cin >> v;
        events.push_back({v, -i});
    }
    sort(events.begin(), events.end());
    set<ll> inds, inds_bar;
    SEG seg;
    seg.make(n);
    for (auto [val, ind] : events) {
        ind = -ind;
        auto x = inds.upper_bound(ind);
        if (x == inds.begin() || *(--x) + d < ind) {
            inds_bar.insert(ind);
        }
        inds.insert(ind);
        auto y = inds_bar.upper_bound(ind);
        if (y != inds_bar.end() && *y <= ind + d) {
            y = inds_bar.erase(y);
        }

        ll lb = *--y;
        seg.set(ind, 1 + seg.query(lb, ind));
    }
    cout << seg.query(0, n-1) << '\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