Submission #417396

#	Time	Username	Problem	Language	Result	Execution time	Memory
417396		lyc	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	214 ms	22904 KiB

event2

#include <bits/stdc++.h>
using namespace std;
 
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;
 
const int mxN = 1e5+5;
const int mxK = 1e5+5;
 
int N, K;
struct Event { int L, R; } events[mxN];
int nxt[2*mxN][18];
vector<int> vals, ans;
 
int solve(int l, int r) {
    l = max(l,0);
    int ret = 0;
    RFOR(i,17,0){
        if (nxt[l][i] <= r) {
            ret += (1<<i);
            l = nxt[l][i];
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
 
    cin >> N >> K;

    FOR(i,1,N){
        int L, R; cin >> L >> R;
        events[i] = {L,R};
        vals.push_back(L);
        vals.push_back(R);
    }

    sort(ALL(vals));
    vals.resize(unique(ALL(vals))-vals.begin());
    int V = SZ(vals);

    FOR(i,0,V) nxt[i][0] = V+1;
    FOR(i,0,17) nxt[V+1][i] = V+1;

    FOR(i,1,N){
        events[i].L = lower_bound(ALL(vals), events[i].L) - vals.begin();
        events[i].R = lower_bound(ALL(vals), events[i].R) - vals.begin();
        nxt[events[i].L][0] = min(nxt[events[i].L][0], events[i].R);
    }
    
    RFOR(i,V-1,0){
        nxt[i][0] = min(nxt[i][0], nxt[i+1][0]);
        FOR(k,1,17){
            nxt[i][k] = nxt[nxt[i][k-1]][k-1];
        }
    }

    //FOR(i,0,V-1){
    //    cout << nxt[i][0] << ' ';
    //}
    //cout << endl;
 
    set<ii> cur;
    cur.insert(ii(-1,-1));
    cur.insert(ii(V,V));
    int take = solve(0,V-1);
    FOR(i,1,N){
        auto& e = events[i];
        auto it = cur.lower_bound(ii(e.L, 0));
        //TRACE(i _ e.L _ e.R _ it->first _ it->second _ take);
        if (e.R > it->first) continue;
        if (prev(it)->second > e.L) continue;
 
        int take2 = take;
        take2 -= solve(prev(it)->second, it->first);
        take2 += solve(prev(it)->second, e.L);
        take2 += solve(e.R, it->first);
        take2 += 1;

        //TRACE(i _ take2);
        if (take2 >= K) {
            cur.insert(ii(e.L,e.R));
            take = take2;
            ans.push_back(i);
        }
 
        if (SZ(ans) == K) break;
    }
 
    if (SZ(ans) < K) {
        cout << -1 << '\n';
    } else {
        for (int& i : ans) {
            cout << i << '\n';
        }
    }
}

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