Submission #1027703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027703		a_l_i_r_e_z_a	LIS (INOI20_lis)	C++17	100 / 100	1125 ms	68832 KiB

Main

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize("avx2")

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy))
#define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy))
#define all(xyxy) (xyxy).begin(), (xyxy).end()
#define len(xyxy) ((int)(xyxy).size())

const int maxn = 1e6 + 5, maxsq = 2e3 + 5, lg = 20;
const int inf = 1e9 + 7;
int n, ans, p[maxn], x[maxn], fen[maxn];
set<pii> st[maxsq];

void upd(int i, int x){
    for(; i < maxn; i += i & -i) fen[i] += x;
}

int get(int x){
    int cur = 0;
    for(int b = lg - 1; b >= 0; b--){
        if(fen[cur + (1ll << b)] < x){
            cur += (1ll << b);
            x -= fen[cur];
        }
    }
    return cur + 1;
}

void dfs(int x, int y, int l){
    smax(ans, l);
    while(st[l].size()){
        auto it = st[l].lower_bound(mp(y, 0));
        if(it == st[l].end()) break;
        if((*it).S > x){
            pii xx = (*it);
            st[l].erase(it);
            dfs(xx.S, xx.F, l + 1);
        }
        else break;
    }
    st[l].insert(mp(y, x));
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> p[i] >> x[i];
    for(int i = 1; i <= n; i++) upd(i, 1);
    for(int i = n - 1; i >= 0; i--){
        p[i] = get(p[i]);
        upd(p[i], -1);
    }
    st[0].insert(mp(0, 0));
    for(int i = 0; i < n; i++){
        int l = 0, r = maxsq;
        while(r - l > 1){
            int mid = (l + r) / 2;
            auto it = st[mid].lower_bound(mp(p[i], 0));
            if(st[mid].size() && it != st[mid].begin()){
                it--;
                if((*it).S < x[i]){
                    l = mid;
                }
                else r = mid;
            }
            else r = mid;
        }
        l++;
        dfs(x[i], p[i], l);
        cout << ans << '\n';
    }

    return 0;
}

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