Submission #1118601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118601		dwuy	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	185 ms	40768 KiB

event2

#include <bits/stdc++.h>
#define int long long 
#define MASK(x) (1LL<<(x))
#define fi first
#define se second

using namespace std;
typedef pair<int, int> pii;

const int MX = 200005;
int n, m, k;
int p[MX][18];
pii a[MX];

int cnt(int l, int r){
    int res = 0;
    for(int i=17; i>=0; i--){
        if(p[r][i] >= l){
            res += MASK(i);
            r = p[r][i];
        }
    }
    return res;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    vector<int> rv;
    for(int i=1; i<=n; i++){
        int l, r;
        cin >> l >> r;
        a[i] = {l, r};
        rv.push_back(l);
        rv.push_back(r);
    }
    sort(rv.begin(), rv.end());
    rv.erase(unique(rv.begin(), rv.end()), rv.end());
    m = rv.size() + 1;
    for(int i=1; i<=n; i++){
        a[i].fi = lower_bound(rv.begin(), rv.end(), a[i].fi + 1) - rv.begin() + 1;
        a[i].se = lower_bound(rv.begin(), rv.end(), a[i].se + 1) - rv.begin() + 1;    
    }
    for(int i=1; i<=n; i++) p[a[i].se][0] = max(p[a[i].se][0], a[i].fi);
    for(int i=1; i<=m; i++) p[i][0] = max(p[i][0], p[i-1][0]);
    for(int j=1; j<18; j++){
        for(int i=1; i<=m; i++) if(p[i][j-1]){
            p[i][j] = p[p[i][j-1]][j-1];
        }
    }
    
    vector<int> ans;
    set<pii> dwuy;
    dwuy.insert({1, 1});
    dwuy.insert({m, m});
    int cur = cnt(1, m);
    for(int i=1; i<=n && k > 0; i++){
        int l = a[i].fi;
        int r = a[i].se;
        auto R = dwuy.lower_bound(a[i]);
        auto L = prev(R);
        if(a[i].se > R->fi) continue;
        if(a[i].fi < L->se) continue;
        int nvpu = cur;
        nvpu -= cnt(L->se, R->fi);
        nvpu += cnt(L->se, a[i].fi);
        nvpu += cnt(a[i].se, R->fi);
        if(nvpu >= k - 1){
            cur = nvpu;
            dwuy.insert(a[i]);
            ans.push_back(i);
            k--;
        }
    }

    if(k) cout << -1;
    else for(int x: ans) cout << x << '\n';

    return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int32_t main()':
event2.cpp:60:13: warning: unused variable 'l' [-Wunused-variable]
   60 |         int l = a[i].fi;
      |             ^
event2.cpp:61:13: warning: unused variable 'r' [-Wunused-variable]
   61 |         int r = a[i].se;
      |             ^

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