Submission #714466

#	Time	Username	Problem	Language	Result	Execution time	Memory
714466		FedShat	Financial Report (JOI21_financial)	C++17	100 / 100	809 ms	28000 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct SegTree {
    struct Node {
        int mn = INF, mnpos = -1;
        int mxdp = -INF;
        int push = -1;

        Node() = default;
        Node(int ri, int i, int dp) {
            mn = ri;
            mnpos = i;
            mxdp = dp;
        }
    };

    Node pull(const Node &a, const Node &b) {
        Node ans;
        ans.mxdp = max(a.mxdp, b.mxdp);
        ans.mn = min(a.mn, b.mn);
        if (a.mn < b.mn) {
            ans.mnpos = a.mnpos;
        } else {
            ans.mnpos = b.mnpos;
        }
        return ans;
    }

    vector<Node> tree;
    int n;

    void push(int v, int l, int r) {
        if (tree[v].push == -1) {
            return;
        }
        if (l + 1 < r) {
            tree[2 * v + 1].push = tree[v].push;
            tree[2 * v + 2].push = tree[v].push;
        }
        if (tree[v].mn != INF) {
            tree[v].mn = tree[v].push;
        }
        tree[v].push = -1;
    }

    void build(int v, int l, int r) {
        if (l + 1 == r) {
            tree[v].mnpos = l;
            return;
        }
        int m = (l + r) / 2;
        build(2 * v + 1, l, m);
        build(2 * v + 2, m, r);
        tree[v] = pull(tree[2 * v + 1], tree[2 * v + 2]);
    }

    SegTree(int n) : n(n) {
        tree.resize(4 * n);
        build(0, 0, n);
    }

    Node get(int v, int l, int r, int li, int ri) {
        push(v, l, r);
        if (li >= r || l >= ri) {
            return {};
        }
        if (li <= l && r <= ri) {
            return tree[v];
        }
        int m = (l + r) / 2;
        return pull(get(2 * v + 1, l, m, li, ri), get(2 * v + 2, m, r, li, ri));
    }

    Node get(int li, int ri) {
        return get(0, 0, n, li, ri);
    }

    void update(int v, int l, int r, int i, const Node &x) {
        push(v, l, r);
        if (i < l || i >= r) {
            return;
        }
        if (l + 1 == r) {
            tree[v] = x;
            return;
        }
        int m = (l + r) / 2;
        update(2 * v + 1, l, m, i, x);
        update(2 * v + 2, m, r, i, x);
        tree[v] = pull(tree[2 * v + 1], tree[2 * v + 2]);
    }

    void update(int i, const Node &x) {
        update(0, 0, n, i, x);
    }

    void update_seg(int v, int l, int r, int li, int ri, int x) {
        push(v, l, r);
        if (li >= r || l >= ri) {
            return;
        }
        if (li <= l && r <= ri) {
            tree[v].push = x;
            push(v, l, r);
            return;
        }
        int m = (l + r) / 2;
        update_seg(2 * v + 1, l, m, li, ri, x);
        update_seg(2 * v + 2, m, r, li, ri, x);
        tree[v] = pull(tree[2 * v + 1], tree[2 * v + 2]);
    }

    void update_seg(int li, int ri, int x) {
        update_seg(0, 0, n, li, ri, x);
    }
};

mt19937 rng(228);

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n = 1e4, d = 1;
    cin >> n >> d;
    vector<int> a(n);
    for (auto &i : a) {
        i = rng() % 100 + 1;
    }
    cin >> a;
    vector<pair<int, int>> coords;
    for (int i = 0; i < n; ++i) {
        coords.push_back({a[i], i});
    }
    sort(coords.begin(), coords.end());
    // for (int i = 0; i < n; ++i) {
    //     a[i] = lower_bound(coords.begin(), coords.end(), pair(a[i], i)) - coords.begin();
    // }
    vector<int> dp(n), ri(n);
    SegTree st(n);
    for (int i = 0; i < n; ++i) {
        dp[i] = 1;
        ri[i] = i;
        while (1) {
            auto cur = st.get(0, n);
            if (i - cur.mn <= d) {
                break;
            }
            st.update(cur.mnpos, {INF, cur.mnpos, -INF});
        }
        {
            int it = lower_bound(coords.begin(), coords.end(), pair(a[i], 0)) - coords.begin();
            auto cur = st.get(0, it);
            dp[i] = max(dp[i], cur.mxdp + 1);
        }
        {
            int it = lower_bound(coords.begin(), coords.end(), pair(a[i], i)) - coords.begin();
            st.update(it, {i, it, dp[i]});
        }
        {
            int it = lower_bound(coords.begin(), coords.end(), pair(a[i], 0)) - coords.begin();
            st.update_seg(it, n, i);
        }
        // for (int j = 0; j < i; ++j) {
        //     if (i - ri[j] <= d && a[j] < a[i]) {
        //         dp[i] = max(dp[i], dp[j] + 1);
        //     }
        // }
        // for (int j = 0; j <= i; ++j) {
        //     if (i - ri[j] <= d && a[j] >= a[i]) {
        //         ri[j] = i;
        //     }
        // }
    }
    for (int i = 0; i < n; ++i) {
        int it = lower_bound(coords.begin(), coords.end(), pair(a[i], i)) - coords.begin();
        ri[i] = st.get(it, it + 1).mn;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (ri[i] == n - 1) {
            ans = max(ans, dp[i]);
        }
    }
    cout << ans << "\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