Submission #1010173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010173		Unforgettablepl	Event Hopping 2 (JOI21_event2)	C++17	39 / 100	1623 ms	6104 KiB

event2

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve1(int n){
    int k;
    cin >> k;
    vector<pair<int,int>> ranges(n);
    vector<int> maxchoose(n+1);
    for(auto&[a,b]:ranges)cin>>a>>b;
    int last = 1e10;
    for(int i=n-1;i>=0;i--){
        if(ranges[i].second<=last){
            last = ranges[i].first;
            maxchoose[i]=maxchoose[i+1]+1;
        } else maxchoose[i]=maxchoose[i+1];
    }
    if(maxchoose[0]<k){
        cout << "-1\n";
        return;
    }
    vector<int> ans;
    int curr = 0;
    for(int i=0;i<n;i++){
        if(curr==k)break;
        int idx = lower_bound(ranges.begin(),ranges.end(),make_pair(ranges[i].second,0ll))-ranges.begin();
        if(curr+1+maxchoose[idx]>=k){ans.emplace_back(i);i=idx-1;curr++;}
    }
    for(int&i:ans)cout<<++i<<'\n';
}

void solve2(int n){
    int k;
    cin >> k;
    vector<pair<int,int>> ranges(n);
    vector<int> maxchoose(n+1);
    map<int,vector<int>> right,left;
    vector<int> val;
    val.emplace_back(0);
    val.emplace_back(1e10);
    int g = 0;
    for(auto&[a,b]:ranges){
        cin>>a>>b;
        left[b].emplace_back(g);
        right[a].emplace_back(g);
        val.emplace_back(a);
        val.emplace_back(b);
        g++;
    }
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    vector<bool> taken(n);
    vector<int> ans;
    map<int,int> lookup;
    int uq = val.size();
    for(int i=0;i<uq;i++)lookup[val[i]]=i;
    vector<int> DPleft(uq),DPright(uq);
    auto calcL = [&](){
        int last = 0;
        for(int i=1;i<uq;i++){
            DPleft[i]=DPleft[i-1];
            for(int&x:left[val[i]])if(!taken[x]){
                if(last<=ranges[x].first){
                    last = ranges[x].second;
                    DPleft[i]++;
                }
            }
        }
    };
    auto calcR = [&](){
        int last = 1e10;
        for(int i=uq-2;i>=0;i--){
            DPright[i]=DPright[i+1];
            for(int&x:right[val[i]])if(!taken[x]){
                if(ranges[x].second<=last){
                    last = ranges[x].first;
                    DPright[i]++;
                }
            }
        }
    };
    calcL();
    if(DPleft[uq-1]<k){
        cout << "-1\n";
        return;
    }
    for(int c=0;c<k;c++){
        calcL();calcR();
        for(int x=0;x<n;x++)if(!taken[x]){
            if(c+1+DPleft[lookup[ranges[x].first]]+DPright[lookup[ranges[x].second]]>=k){
                taken[x]=true;
                ans.emplace_back(x);
                for(int j=0;j<n;j++)if(min(ranges[x].second,ranges[j].second)-max(ranges[x].first,ranges[j].first)>0)taken[j]=true;
                break;
            }
        }
    }
    for(int&i:ans)cout<<++i<<'\n';
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    if(n<=5000)solve2(n);
    else solve1(n);
}

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