Submission #1270887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270887		tvgk	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	521 ms	24168 KiB

event2

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7, inf = 1e9 + 7;

int n, jump[mxN][25], k;
ii tree[mxN * 4], a[mxN], arr[mxN];
set<ii> s;

void Build(int j = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        tree[j] = {a[l].se, l};
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    tree[j] = min(tree[j * 2], tree[j * 2 + 1]);
}

ii Get(int vt, int j = 1, int l = 1, int r = n)
{
    if (vt <= a[l].fi)
        return tree[j];

    if (a[r].fi < vt)
        return {inf, n + 1};

    int mid = (l + r) / 2;
    return min(Get(vt, j * 2, l, mid), Get(vt, j * 2 + 1, mid + 1, r));
}

int Count(int l, int r)
{
    int res = 0;

    int cur = Get(l).se;
    for (int i = 20; i >= 0; i--)
    {
        if (cur == n + 1)
            break;

        if (jump[cur][i] <= r)
        {
            res += 1 << i;
            cur = Get(jump[cur][i]).se;
        }
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fi >> a[i].se;
        arr[i] = a[i];
    }
    sort(a + 1, a + n + 1);
    Build();

    for (int i = n; i >= 1; i--)
    {
        jump[i][0] = a[i].se;
        for (int j = 1; j <= 20; j++)
        {
            int nxt = Get(jump[i][j - 1]).se;
            if (nxt == n + 1)
                jump[i][j] = inf;
            else
                jump[i][j] = jump[nxt][j - 1];
        }
    }

    int mx = Count(1, 1e9);
    s.insert({0, 0});
    s.insert({1, 1e9});

    if (mx < k)
    {
        cout << -1;
        return 0;
    }

    for (int i = 1; i <= n; i++)
    {
        ii seg = *(--s.upper_bound(ii(arr[i].fi, inf)));

        if (seg.se < arr[i].se || !k)
            continue;

        int nw = mx - Count(seg.fi, seg.se) + Count(seg.fi, arr[i].fi) + Count(arr[i].se, seg.se);
        if (nw < k - 1)
            continue;

        mx = nw;
        k--;
        s.erase(seg);
        s.insert({seg.fi, arr[i].fi});
        s.insert({arr[i].se, seg.se});

        cout << i << '\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61