Submission #999583

#	Time	Username	Problem	Language	Result	Execution time	Memory
999583		Nelt	LIS (INOI20_lis)	C++17	100 / 100	1442 ms	135508 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"

using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e6 + 5;
ll t[N];
set<pair<ll, ll>> v[N];
void upd(ll v)
{
    for (; v < N; v |= (v + 1)) t[v]++;
}
ll sum(ll v)
{
    ll ans = 0;
    for (; v >= 0; v = (v & (v + 1)) - 1) ans += t[v];
    return ans;
}
ll ans = 1;
void f(pair<ll, ll> x, ll lis)
{
    ans = max(ans, lis);
    while (!v[lis].empty() and v[lis].lower_bound(make_pair(x.first, -1)) != v[lis].end() and v[lis].lower_bound(make_pair(x.first, -1))->second > x.second)
        f(*v[lis].lower_bound(make_pair(x.first, -1)), lis + 1), v[lis].erase(*v[lis].lower_bound(make_pair(x.first, -1)));
    v[lis].insert(x);
}
void solve()
{
    ll q;
    cin >> q;
    pair<ll, ll> qs[q];
    for (ll i = 0; i < q; i++)
        cin >> qs[i].first >> qs[i].second;
    for (ll i = q - 1; i >= 0; i--)
    {
        ll l = 1, r = q;
        while (l <= r)
        {
            ll mid = (l + r) >> 1;
            if (mid - sum(mid) >= qs[i].first) 
                r = mid - 1;
            else l = mid + 1;
        }
        qs[i].first = l;
        upd(qs[i].first);
    }
    for (auto [p, x] : qs)
    {
        ll mx = 1;
        for (ll i = x - 1; i >= 1; i--)
            if (!v[i].empty() and v[i].begin()->first < p)
            {
                auto pos = *--v[i].lower_bound(make_pair(p, -1));
                if (pos.second < x)
                {
                    mx = i + 1;
                    break;
                }
            }
        ans = max(ans, mx);
        f(make_pair(p, x), mx);
        cout << ans << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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