Submission #756775

#	Time	Username	Problem	Language	Result	Execution time	Memory
756775		Dan4Life	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	179 ms	22728 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)2e5+10;
const int mxLg = 20;
int n, k;
vector<int> v;
int L[mxN], R[mxN];
int jmp[mxLg][mxN*2];
set<pair<int,int>> S;

int get(int l, int r){
    int tot = 0;
    for(int i = mxLg-1; i>=0; i--)
        if(jmp[i][l]<=r) l=jmp[i][l], tot+=(1<<i);
    return tot;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> L[i] >> R[i], v.pb(L[i]), v.pb(R[i]);
    sort(all(v)); v.erase(unique(all(v)),end(v));
    for(int i = 0; i <= sz(v); i++) jmp[0][i]=sz(v);
    for(int i = 1; i <= n; i++){
        L[i] = lower_bound(all(v),L[i])-begin(v);
        R[i] = lower_bound(all(v),R[i])-begin(v);
        jmp[0][L[i]] = min(jmp[0][L[i]],R[i]);
    }
    for(int i = sz(v)-1; i>=0; i--)
        jmp[0][i]=min(jmp[0][i],jmp[0][i+1]);
    for(int i = 1; i < mxLg; i++)
        for(int j = 0; j <= sz(v); j++)
            jmp[i][j] = jmp[i-1][jmp[i-1][j]];
    int tot = get(0,sz(v)-1); if(tot<k){cout<<-1;return 0;}
    S.insert({0,0}), S.insert({sz(v)-1,sz(v)-1});
    for(int i = 1; i <= n; i++){
        auto itr = S.lower_bound({R[i],0});
        int r = itr->first, l = (--itr)->second;
        int num = tot-get(l,r)+get(l,L[i])+get(R[i],r)+1;
        if(L[i]>=l and num>=k){
            cout << i << "\n"; tot=num;
            S.insert({L[i],R[i]});
            if(sz(S)==k+2) break;
        }
    }
}

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