제출 #1298694

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

Main

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

const int MX = 1e6 + 5, INF = 1e9;

int n, p[MX], val[MX], tpos[MX], a[MX], T, N;

struct Convert {
    int seg[MX<<2];
    void build(int l, int r, int id){
        seg[id] = r - l;
        if(r - l == 1) return;
        int m = (l+r)>>1;
        build(l, m, id<<1);
        build(m, r, id<<1|1);
    }
    void upd(int p, int l, int r, int id){
        seg[id]--;
        if(r - l == 1) return;
        int m = (l+r)>>1;
        p < m ? upd(p, l, m, id<<1) : upd(p, m, r, id<<1|1);
    }
    int kth(int k, int l, int r, int id){
        if(r - l == 1) return l;
        int m = (l+r)>>1;
        if(seg[id<<1] >= k) return kth(k, l, m, id<<1);
        return kth(k - seg[id<<1], m, r, id<<1|1);
    }
    void run(){
        build(1, n+1, 1);
        for(int i = n; i >= 1; i--){
            p[i] = kth(p[i], 1, n+1, 1);
            upd(p[i], 1, n+1, 1);
        }
    }
} conv;

struct Seg {
    vector<int> st;
    Seg(){}
    Seg(int n){ st.assign(4*n+5, INF); }
    void upd(int p, int v, int l, int r, int id){
        if(r - l == 1){
            st[id] = min(st[id], v);
            return;
        }
        int m = (l+r)>>1;
        p < m ? upd(p, v, l, m, id<<1) : upd(p, v, m, r, id<<1|1);
        st[id] = min(st[id<<1], st[id<<1|1]);
    }
    int get(int s, int e, int l, int r, int id){
        if(s >= r || l >= e) return INF;
        if(s <= l && r <= e) return st[id];
        int m = (l+r)>>1;
        return min(get(s, e, l, m, id<<1), get(s, e, m, r, id<<1|1));
    }
} seg[1505];

int res[MX];

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

    cin >> n;
    vector<int> comp;
    for(int i=1;i<=n;i++){
        cin >> p[i] >> val[i];
        comp.push_back(val[i]);
    }

    conv.run();

    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    N = comp.size();

    for(int i=1;i<=n;i++){
        a[p[i]] = lower_bound(comp.begin(), comp.end(), val[i]) - comp.begin() + 1;
        tpos[p[i]] = i;
    }

    for(int i=1;i<=N;i++) seg[i] = Seg(N);

    for(int i=1;i<=n;i++){
        seg[1].upd(a[i], tpos[i], 1, N+1, 1);
        for(int j=2;j<=a[i];j++){
            int v = seg[j-1].get(1, a[i], 1, N+1, 1);
            seg[j].upd(a[i], max(v, tpos[i]), 1, N+1, 1);
        }
    }

    for(int k=1;k<=N;k++){
        int tm = seg[k].st[1];
        if(tm < INF) res[tm] = k;
    }

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

    return 0;
}

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