Submission #1060445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060445		vjudge1	LIS (INOI20_lis)	C++14	100 / 100	1313 ms	152508 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e6+7;
ll n, st[mxn<<2], dp[mxn], a[mxn], ans = 0;
vector<pair<ll,ll>> qx;
vector<set<ll>> opt(mxn);
void build(ll id, ll l, ll r)
{
    st[id] = r-l+1;
    if (l == r) {return;}
    ll m = (r+l)>>1;
    build(id<<1,l,m); build(id<<1|1,m+1,r);
}
void upd(ll id, ll l, ll r, ll i)
{
    if (r < i || i < l) return;
    if (l == r) {st[id] = 0; return;}
    ll m = (r+l)>>1;
    upd(id<<1,l,m,i); upd(id<<1|1,m+1,r,i);
    st[id] = st[id<<1]+st[id<<1|1];
}
ll walk(ll id, ll l, ll r, ll x)
{
    if (l == r) return l;
    ll m = (r+l)>>1;
    if (st[id<<1] >= x) return walk(id<<1,l,m,x);
    return walk(id<<1|1,m+1,r,x-st[id<<1]);
}
void lis_update(ll p)
{
    ans = max(ans, dp[p]);
    set<ll>::iterator f = opt[dp[p]].upper_bound(p);
    while (f != opt[dp[p]].end() && a[*f] > a[p])
    {
        ll cpy = *f;
        opt[dp[p]].erase(cpy);
        dp[cpy] = dp[p]+1;
        lis_update(cpy);
        f = opt[dp[p]].upper_bound(p);
    }
    opt[dp[p]].insert(p);
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n; build(1,1,n); qx.emplace_back();
    for (ll i = 1; i <= n; i++) 
    {
        ll p, x; cin >> p >> x;
        qx.pb({p,x});
    }
    for (ll i = n; i >= 1; i--)
    {
        ll pos = walk(1,1,n,qx[i].fi);
        qx[i].fi = pos; a[pos] = qx[i].se;
        upd(1,1,n,pos);
    }
    for (ll i = 1; i <= n; i++)
    {
        dp[qx[i].fi] = 1; // lis up to i-th
        for (ll j = 1; j < qx[i].se; j++) 
        {
            set<ll>::iterator it = opt[j].lower_bound(qx[i].fi);
            if (it == opt[j].begin()) continue;
            --it;
            if (a[*it] < qx[i].se) dp[qx[i].fi] = j+1; 
        }
        lis_update(qx[i].fi);
        cout << ans << '\n';
    }
}

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