oj.uz

Submission #760210

# Submission time Handle Problem Language Result Execution time Memory
760210 2023-06-17T09:58:14 Z drdilyor LIS (INOI20_lis) C++17
20 / 100
 4000 ms 12104 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 5 ms 8020 KB Output is correct
3 Correct 383 ms 8220 KB Output is correct
4 Correct 398 ms 8148 KB Output is correct
5 Correct 393 ms 8224 KB Output is correct
6 Correct 379 ms 8240 KB Output is correct
7 Correct 392 ms 8228 KB Output is correct
8 Correct 386 ms 8148 KB Output is correct
9 Correct 400 ms 8228 KB Output is correct
10 Correct 384 ms 8224 KB Output is correct
11 Correct 396 ms 8224 KB Output is correct
12 Correct 377 ms 8148 KB Output is correct
13 Correct 395 ms 8148 KB Output is correct
14 Correct 390 ms 8228 KB Output is correct
15 Correct 383 ms 8232 KB Output is correct
16 Correct 390 ms 8224 KB Output is correct
17 Correct 399 ms 8148 KB Output is correct
18 Correct 389 ms 8232 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 5 ms 8020 KB Output is correct
3 Correct 383 ms 8220 KB Output is correct
4 Correct 398 ms 8148 KB Output is correct
5 Correct 393 ms 8224 KB Output is correct
6 Correct 379 ms 8240 KB Output is correct
7 Correct 392 ms 8228 KB Output is correct
8 Correct 386 ms 8148 KB Output is correct
9 Correct 400 ms 8228 KB Output is correct
10 Correct 384 ms 8224 KB Output is correct
11 Correct 396 ms 8224 KB Output is correct
12 Correct 377 ms 8148 KB Output is correct
13 Correct 395 ms 8148 KB Output is correct
14 Correct 390 ms 8228 KB Output is correct
15 Correct 383 ms 8232 KB Output is correct
16 Correct 390 ms 8224 KB Output is correct
17 Correct 399 ms 8148 KB Output is correct
18 Correct 389 ms 8232 KB Output is correct
19 Execution timed out 4073 ms 12104 KB Time limit exceeded
20 Halted 0 ms 0 KB -