제출 #1003289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003289		12345678	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	100 ms	16000 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;
set<range> 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];
    vl=query(0, inf);
    if (vl<k) return cout<<-1, 0;
    cur.insert(range(0, 0));
    for (int i=1; i<=n; i++)
    {
        if (!k) continue;
        auto itr=cur.upper_bound(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.insert(range(a[i], b[i]));
            vl=tmp;
            cout<<i<<'\n';
        }
    }
}

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