Submission #760210

#	Time	Username	Problem	Language	Result	Execution time	Memory
760210		drdilyor	LIS (INOI20_lis)	C++17	20 / 100	4073 ms	12104 KiB

Main

#include<bits/extc++.h>
using namespace std;
namespace pbds = __gnu_pbds;

struct SegmentTree {
    using T = int;
    using S = int;
    const T id = {};
    inline T single(S v) { return v; }

    T merge(const T& l, const T& r) {
        return max(l, r);
    }

    int n;
    vector<T> tree;

    SegmentTree(int n) : n(n) {
        tree.resize(n * 2, id);
        build();
    }
    SegmentTree(vector<S> arr) : n(arr.size()) {
        tree.resize(n * 2, id);
        for (int i = 0; i < n; i++) {
            tree[i + n] = single(arr[i]);
        }
        build();
    }

    void build() {
        for (int i = n-1; i >= 1; i--) {
            tree[i] = merge(tree[i*2], tree[i*2 + 1]);
        }
    }

    void update(int i, S v) {
        tree[i+=n] = single(v);
        for (i /= 2; i >= 1; i/= 2)
            tree[i] = merge(tree[i*2], tree[i*2+1]);
    }

    T query(int l, int r) {
        T left = id, right = id;
        l += n;
        r += n;
        while (l <= r) {
            if (l % 2 == 1) left = merge(left, tree[l++]);
            if (r % 2 == 0) right = merge(right, tree[r--]);
            l /= 2; r /= 2;
        }
        return merge(left, right);
    }

    int find_first(function<bool(T&)> predicate, int last = 0) {
        int v = 1;
        while (v < n) {
            if (predicate(tree[v*2 + last])) v = v*2 + last;
            else if (predicate(tree[v*2 + !last])) v = v*2 + !last;
            else return -1;
        }
        return v;
    }
};



int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> arr(n);
    for (auto& [p, x] : arr) cin >> p >> x, p--;

    pbds::tree<int, pbds::null_type, less<int>, pbds::rb_tree_tag, pbds::tree_order_statistics_node_update>
        st;
    for (int i = 0; i < n;i++)
        st.insert(i);
    reverse(arr.begin(), arr.end());
    for (auto &[p, x] : arr) {
        auto it = st.find_by_order(p);
        p = *it+1;
        st.erase(it);
    }
    reverse(arr.begin(), arr.end());
    
#ifdef ONPC
    for (auto &[p, x] : arr) {
        cout << p << ' ' << x << endl;
    }

    cout <<"---" << endl;
#endif

    vector<int> pot(n+1);

    SegmentTree rev((int)1e6+1);
    for (auto [p, x] : arr) {
        pot[p] = x;
        vector<int> dp(pot.size());
        for (int i = 0; i < (int)pot.size(); i++) {
            dp[i] = 1+rev.query(0, pot[i]-1);
            rev.update(pot[i], max(rev.query(pot[i], pot[i]), dp[i]));
        }
        cout << *max_element(dp.begin(), dp.end())-1 << '\n';
        for (int i : pot)
            rev.update(i, 0);
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80