Submission #1094555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094555		vladilius	Event Hopping 2 (JOI21_event2)	C++17	39 / 100	154 ms	31052 KiB

event2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k; cin>>n>>k;
    vector<int> l(n + 1), r(n + 1), all1;
    for (int i = 1; i <= n; i++){
        cin>>l[i]>>r[i];
        all1.pb(l[i]);
        all1.pb(r[i]);
    }
    
    sort(all1.begin(), all1.end());
    vector<int> all;
    for (int i: all1){
        if (all.empty() || all.back() != i){
            all.pb(i);
        }
    }
    
    vector<int> :: iterator it;
    for (int i = 1; i <= n; i++){
        it = lower_bound(all.begin(), all.end(), l[i]);
        l[i] = (int) (it - all.begin()) + 1;
        it = lower_bound(all.begin(), all.end(), r[i]);
        r[i] = (int) (it - all.begin()) + 1;
    }
    
    // i -> j: r[i] <= l[j]
    int N = (int) all.size();
    vector<arr3> t;
    vector<int> bg[N + 1];
    for (int i = 1; i <= n; i++){
        t.pb({l[i], r[i], i});
        bg[l[i]].pb(i);
    }
    sort(t.begin(), t.end());
    
    vector<pii> mn(N + 1, {N + 1, 0});
    for (int i = N - 1; i > 0; i--){
        mn[i] = mn[i + 1];
        for (int j: bg[i]){
            mn[i] = min(mn[i + 1], {r[j], j});
        }
    }
    
    vector<int> g(n + 1);
    for (int i = n - 1; i >= 0; i--){
        auto [x, y, ii] = t[i];
        g[ii] = mn[y].ss;
    }
    
    const int lg = log2(n);
    vector<vector<int>> pw(n + 1, vector<int>(lg + 1));
    for (int i = n - 1; i >= 0; i--){
        int ii = t[i][2];
        pw[ii][0] = g[ii];
        for (int j = 1; j <= lg; j++){
            pw[ii][j] = pw[pw[ii][j - 1]][j - 1];
        }
    }
    
    auto get = [&](int x, int y){
        int p = mn[x].ss, cc = 0;
        for (int i = lg; i >= 0; i--){
            int pp = pw[p][i];
            if (!pp) continue;
            if (r[pp] <= y){
                cc += (1 << i);
                p = pp;
            }
        }
        while (p > 0 && r[p] <= y){
            cc++; p = g[p];
        }
        return cc;
    };
    
    vector<int> out;
    set<pii> st;
    int tot = get(1, N);
    for (int i = 1; i <= n; i++){
        if (out.size() == k) break;
        int x = 1, y = N;
        auto it = st.lower_bound({r[i], 0});
        if (it != st.end()){
            y = (*it).ff;
            if (y < r[i]) continue;
        }
        if (it != st.begin()){
            it--;
            x = (*it).ss;
            if (l[i] < x) continue;
        }

        int sum = tot + 1 - get(x, y) + get(x, l[i]) + get(r[i], y);

        if (sum >= k){
            out.pb(i);
            st.insert({l[i], r[i]});
            tot = sum;
        }
    }
    
    if (out.size() < k){
        cout<<-1<<"\n";
        return 0;
    }
    for (int i: out) cout<<i<<" ";
    cout<<"\n";
}

Compilation message (stderr)

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

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