Submission #1003273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003273		12345678	Event Hopping 2 (JOI21_event2)	C++17	7 / 100	47 ms	12496 KiB

event2

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=17, inf=2e9;

int n, k, a[nx], b[nx], pa[nx][kx], mx, vl;

struct range
{
    int l, r;
    range(int l, int r): l(l), r(r){}
    bool operator< (const range &o) const
    {
        if (r==o.r) return l<o.l;
        return r<o.r;
    }
};
vector<range> v, cur;

int query(int u, int limit)
{
    int res=0;
    if (limit==inf) limit--;
    for (int i=kx-1; i>=0; i--) if (v[pa[u][i]].r<=limit) res+=(1<<i), u=pa[u][i];
    return res;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    v.push_back(range(0, 0));
    for (int i=1; i<=n; i++) cin>>a[i]>>b[i], v.push_back(range(a[i], b[i])), pa[i][0]=n+1;
    v.push_back(range({inf, inf}));
    sort(v.begin(), v.end());
    int lst=0;
    for (int i=1; i<=n+1; i++)
    {
        mx=max(mx, v[i].l);
        while (lst<=n+1&&v[lst].r<=mx) pa[lst++][0]=i;
    }
    for (int i=1; i<kx; i++) for (int j=0; j<=n+1; j++) pa[j][i]=pa[pa[j][i-1]][i-1];
    /*
    for (int i=0; i<=n+1; i++)
    {
        cout<<"debug "<<i<<' '<<v[i].l<<' '<<v[i].r<<':';
        for (int j=0; j<=2; j++) cout<<pa[i][j]<<' ';
        cout<<'\n';
    }
    */
    vl=query(0, inf);
    if (vl<k) return cout<<-1, 0;
    cur.push_back(range(0, 0));
    for (int i=1; i<=n; i++)
    {
        if (!k) continue;
        auto itr=upper_bound(cur.begin(), cur.end(), range(a[i], b[i]));
        if (itr!=cur.end()&&itr->l<b[i]) continue;
        if (prev(itr)->r>a[i]) continue;
        int tmp=vl, pidx=lower_bound(v.begin(), v.end(), *prev(itr))-v.begin(), cidx=lower_bound(v.begin(), v.end(), range(a[i], b[i]))-v.begin();
        tmp-=query(pidx, (itr==cur.end())?inf:itr->l);
        tmp+=query(pidx, a[i]);
        tmp+=query(cidx, (itr==cur.end())?inf:itr->l);
        //cout<<"vl "<<i<<' '<<tmp<<'\n';
        if (tmp>=k-1)
        {
            k--;
            cur.push_back(range(a[i], b[i]));
            vl=tmp;
            cout<<i<<'\n';
        }
    }
}

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