Submission #1286316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286316		denislav	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	146 ms	23928 KiB

event2

# include <iostream>
# include <vector>
# include <algorithm>
# include <set>
using namespace std;

const int MAX=2e5+11,LOG=20,INF=1e9;

int n,k;
pair<int,int> a[MAX];

int st[MAX][LOG];

void sparse_table()
{
    for(int i=0;i<=n*2+1;i++) st[i][0]=INF;

    vector<pair<int,int>> v;
    for(int i=1;i<=n;i++)
    {
        v.push_back({a[i].first,i});
        v.push_back({a[i].second,-i});
    }
    sort(v.rbegin(),v.rend());

    int to=INF;
    for(pair<int,int> pa: v)
    {
        if(pa.second<0) st[pa.first][0]=to;
        else to=min(to,a[pa.second].second);
    }
    st[0][0]=to;

    for(int i=n*2;i>=0;i--) st[i][0]=min(st[i][0],st[i+1][0]);
    for(int j=1;j<LOG;j++)
    {
        for(int i=0;i<=n*2;i++)
        {
            if(st[i][j-1]==INF or st[st[i][j-1]][j-1]==INF) st[i][j]=INF;
            else st[i][j]=st[st[i][j-1]][j-1];
        }
    }

    //for(int i=0;i<=n*2;i++) cout<<i<<":"<<st[i][0]<<"\n";
}

int lift(int r, int to)
{
    int ans=0;
    for(int j=LOG-1;j>=0;j--)
    {
        if(st[r][j]<=to)
        {
            ans+=(1<<j);
            r=st[r][j];
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>k;
    vector<pair<int,int>> compr;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].first>>a[i].second;
        compr.push_back({a[i].first,i});
        compr.push_back({a[i].second,-i});
    }
    sort(compr.begin(),compr.end());
    int last=-1,ct=0;
    for(pair<int,int> pa: compr)
    {
        if(pa.first!=last)
        {
            ct++;
            last=pa.first;
        }
        if(pa.second>=0) a[pa.second].first=ct;
        else a[-pa.second].second=ct;
    }
    sparse_table();

    //for(int i=1;i<=n;i++) cout<<a[i].first<<" "<<a[i].second<<"\n";

    int curr=lift(0,n*2);
    set<pair<int,int>> s={{0,0},{n*2,n*2}};
    vector<int> ans;
    for(int i=1;i<=n;i++)
    {
        if((int)s.size()==k+2) break;

        if(s.find(a[i])!=s.end()) continue;
        s.insert(a[i]);
        auto it=s.find(a[i]),itL=it,itR=it;
        itL--;itR++;
        int r=(itL->second),l=(itR->first);

        if(r>a[i].first or l<a[i].second)
        {
            s.erase(a[i]);
            continue;
        }

        int delta=lift(r,a[i].first)+1+lift(a[i].second,l)-lift(r,l);
        if(curr+delta>=k)
        {
            ans.push_back(i);
            curr+=delta;
        }
        else s.erase(a[i]);
    }

    if((int)ans.size()==k)
    {
        for(int x: ans) cout<<x<<"\n";
    }
    else cout<<-1<<"\n";

    return 0;
}

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