Submission #1011907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011907		Unforgettablepl	Event Hopping 2 (JOI21_event2)	C++17	7 / 100	172 ms	46904 KiB

event2

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

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin >> n >> k;
    vector<int> sortedidx(n);
    map<pair<int,int>,int> actidx;
    vector<pair<int,int>> ranges(n);
    for(auto&[a,b]:ranges)cin>>b>>a;
    for(int i=0;i<n;i++)actidx[ranges[i]] = i;
    sort(ranges.begin(),ranges.end());
    for(int i=0;i<n;i++)sortedidx[actidx[ranges[i]]] = i;
    for(auto&[a,b]:ranges)swap(a,b);
    vector<vector<int>> lift(n+2,vector<int>(17));
    set<pair<int,int>> curr;
    curr.insert({1e10,n});
    lift[n][0]=n;
    lift[n+1][0]=0;
    for(int i=n-1;i>=0;i--){
        lift[i][0] = curr.lower_bound({ranges[i].second,0ll})->second;  
        while(curr.begin()->first<=ranges[i].first)curr.erase(curr.begin());
        curr.insert({ranges[i].first,i});
    }
    ranges.emplace_back(1e10,1e10+1);
    ranges.emplace_back(-1,0);
    for(int bit=1;bit<=16;bit++){
        for(int i=0;i<=n+1;i++){
            lift[i][bit] = lift[lift[i][bit-1]][bit-1];
        }
    }
    auto get = [&](int x,int r){
        int ans = 0;
        for(int jump=16;jump>=0;jump--){
            if(ranges[lift[x][jump]].second<=r){
                x = lift[x][jump];
                ans+=1<<jump;
            }
        }
        return ans;
    };
    if(get(n+1,1e9)<k){
        cout << "-1\n";
        return 0;
    }
    vector<int> ans;
    int currsum = get(n+1,1e9);
    set<tuple<int,bool,int>> points; // True is left, false is right
    points.insert({0,false,n+1}); 
    points.insert({1e10,true,n}); 
    for(int i=0;i<n;i++){
        int idx = sortedidx[i];
        auto [r,type,rx] = *points.upper_bound({ranges[idx].first,false,n+3});
        if(type==false)continue;
        if(r<ranges[idx].second)continue;
        auto [l,t,lx] = *(--points.upper_bound({ranges[idx].first,false,n+3}));
        int delta = -get(lx,r)+1+get(lx,ranges[idx].first)+get(idx,r);
        if(currsum+delta>=k){
            currsum+=delta;
            ans.emplace_back(i);
            points.insert({ranges[idx].first,true,idx});
            points.insert({ranges[idx].second,false,idx});
            if(ans.size()==k)break;
        }
    }
    for(int&i:ans)cout<<++i<<'\n';
}

Compilation message (stderr)

event2.cpp: In function 'int32_t main()':
event2.cpp:68:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   68 |             if(ans.size()==k)break;
      |                ~~~~~~~~~~^~~

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