제출 #1268404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268404		Hamed_Ghaffari	LIS (INOI20_lis)	C++20	100 / 100	435 ms	34296 KiB

Main

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

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 1e6+5, inf = 1e9;

int n;

namespace converter {
    int seg[MXN<<2];
    void build(int l=1, int r=n+1, int id=1) {
        seg[id] = r-l;
        if(r-l == 1) return;
        build(l, mid, lc);
        build(mid, r, rc);
    }
    void upd(int p, int l=1, int r=n+1, int id=1) {
        seg[id]--;
        if(r-l==1) return;
        p<mid ? upd(p, l, mid, lc) : upd(p, mid, r, rc);
    }
    int kth(int k, int l=1, int r=n+1, int id=1) {
        if(r-l==1) return l;
        return seg[lc]>=k ? kth(k, l, mid, lc) : kth(k-seg[lc], mid, r, rc);
    }
    inline void convert(int p[MXN]) {
        build();
        for(int i=n; i>=1; i--) upd(p[i] = kth(p[i]));
    }
}

int p[MXN], a[MXN], b[MXN], t[MXN], ans[MXN], N;
vector<int> cmp;

inline int GI(int x) { return lower_bound(cmp.begin(), cmp.end(), x)-cmp.begin()+1; }

struct Seg {
    vector<int> seg;
    void upd(int p, int x, int l=1, int r=N+1, int id=1) {
        if(r-l == 1) {
            seg[id] = min(seg[id], x);
            return;
        }
        p<mid ? upd(p, x, l, mid, lc) : upd(p, x, mid, r, rc);
        seg[id] = min(seg[lc], seg[rc]);
    }
    int get(int s, int e, int l=1, int r=N+1, int id=1) {
        if(s>=r || l>=e) return inf;
        if(s<=l && r<=e) return seg[id];
        return min(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
    }
} seg[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> p[i] >> b[i], cmp.push_back(b[i]);
    converter::convert(p);
    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end())-cmp.begin());
    for(int i=1; i<=n; i++) {
        a[p[i]] = GI(b[i]);
        t[p[i]] = i;
    }
    N = cmp.size();
    for(int i=1; i<=N; i++) seg[i].seg = vector<int>(4*N+5, inf);
    for(int i=1; i<=n; i++) {
        seg[1].upd(a[i], t[i]);
        for(int j=2; j<=a[i]; j++)
            seg[j].upd(a[i], max(t[i], seg[j-1].get(1, a[i])));
    }
    for(int i=1; i<=N; i++)
        if(seg[i].seg[1]!=inf)
            ans[seg[i].seg[1]] = i;
    for(int i=1; i<=n; i++) {
        ans[i] = max(ans[i-1], ans[i]);
        cout << ans[i] << '\n';
    }
    return 0;
}

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