Submission #1207711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207711		tamzid	LIS (INOI20_lis)	C++20	20 / 100	4094 ms	944 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;

    vector<int> seq;

    for (int i = 0; i < q; ++i) {
        int pos, x;
        cin >> pos >> x;

        // Insert x at the (pos - 1) index
        seq.insert(seq.begin() + (pos - 1), x);

        // Compute LIS using patience sorting method (O(n log n))
        vector<int> lis;
        for (int num : seq) {
            auto it = lower_bound(lis.begin(), lis.end(), num);
            if (it == lis.end()) {
                lis.push_back(num);
            } else {
                *it = num;
            }
        }

        cout << lis.size() << '\n';
    }

    return 0;
}

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