제출 #1298687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298687		imanghader	LIS (INOI20_lis)	C++20	0 / 100	1 ms	332 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;
    vector<int> st;
    const int INF = 1e9;

    SegTree(int n=0) { init(n); }
    void init(int n_) {
        n = n_;
        st.assign(4*n + 5, INF);
    }

    void update(int idx, int val, int p, int l, int r) {
        if (l == r) {
            st[p] = min(st[p], val);
            return;
        }
        int mid = (l+r)/2;
        if (idx <= mid) update(idx, val, p*2, l, mid);
        else update(idx, val, p*2+1, mid+1, r);
        st[p] = min(st[p*2], st[p*2+1]);
    }
    void update(int idx, int val) { update(idx, val, 1, 1, n); }

    int query(int ql, int qr, int p, int l, int r) {
        if (qr < l || r < ql) return INF;
        if (ql <= l && r <= qr) return st[p];
        int mid = (l+r)/2;
        return min(query(ql, qr, p*2, l, mid),
                   query(ql, qr, p*2+1, mid+1, r));
    }
    int query(int l, int r) {
        if (l > r) return 1e9;
        return query(l, r, 1, 1, n);
    }
};

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

    int q;
    cin >> q;
    vector<pair<int,int>> ops(q+1);
    for (int i=1; i<=q; i++) cin >> ops[i].first >> ops[i].second;

    vector<pair<int,int>> arr;  
    arr.reserve(q);
    for (int i=1; i<=q; i++) {
        int pos = ops[i].first;
        int x = ops[i].second;
        arr.insert(arr.begin() + (pos-1), {x, i});
    }

    vector<int> comp;
    comp.reserve(q);
    for (auto &p : arr) comp.push_back(p.first);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());

    int C = comp.size(); 

    for (auto &p : arr)
        p.first = int(lower_bound(comp.begin(), comp.end(), p.first) - comp.begin()) + 1;

    int MAXL = int(sqrt(q)) + 3;

    vector<SegTree> trees(MAXL, SegTree(C));

    vector<int> ans(q+1, 1);
    int global_LIS = 1;

    for (auto &[val, t] : arr) {
        for (int l = min(val, MAXL-1); l >= 1; l--) {
            int best_prev = (l == 1 ? 0 : trees[l-1].query(1, val-1));
            int new_time = max(t, best_prev);
            trees[l].update(val, new_time);
            ans[t] = max(ans[t], l);
            global_LIS = max(global_LIS, l);
        }
    }

    int cur = 1;
    for (int i=1; i<=q; i++) {
        cur = max(cur, ans[i]);
        cout << cur << "\n";
    }
}

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