Submission #1067608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067608		VMaksimoski008	Financial Report (JOI21_financial)	C++17	5 / 100	310 ms	27388 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct SegTree {
    int n;
    vector<int> tree;

    SegTree(int _n) : n(_n), tree(4*_n+5) { }

    void update(int u, int tl, int tr, int p, int v) {
        if(tl == tr) {
            tree[u] = max(tree[u], v);
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) update(2*u, tl, tm, p, v);
            else update(2*u+1, tm+1, tr, p, v);
            tree[u] = max(tree[2*u], tree[2*u+1]);
        }
    }

    int query(int u, int tl, int tr, int l, int r) {
        if(l > tr || tl > r) return 0;
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return max(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

    void update(int p, int v) { update(1, 1, n, p, v); }
    int query(int l, int r) { return query(1, 1, n, l, r); }
};

signed main() {
    int n, d;
    cin >> n >> d;

    vector<int> v(n+1), dp(n+1); set<int> s;
    for(int i=1; i<=n; i++) cin >> v[i], s.insert(v[i]);

    vector<pii> vec;
    for(int i=1; i<=n; i++) vec.push_back({ v[i], i });

    sort(vec.begin(), vec.end(), [&](pii &a, pii &b) {
        if(a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    });

    SegTree tree(n);
    for(int i=0; i<n; i++) {
        dp[vec[i].second] = tree.query(max(1, vec[i].second-d), vec[i].second-1) + 1;
        tree.update(vec[i].second, dp[vec[i].second]);
    }

    cout << *max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}

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