Submission #1097929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097929		thangdz2k7	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	127 ms	25296 KiB

event2

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fd(sr, x) (lower_bound(sr.begin(), sr.end(), x) - sr.begin())
#define uq(sr) (sr).erase(unique(all((sr))), (sr).end())
#define szv(v) (int((v).size()))

int n, k, l[N], r[N], to[N][20];

int get(int u, int v){
    int ans = 0;
    for (int l = LG - 1; l >= 0; -- l){
        if (to[u][l] <= v){
            ans += (1 << l);
            u = to[u][l] + 1;
        }
    }
    return ans;
}

void solve(){
    cin >> n >> k; vi sr;
    for (int i = 1; i <= n; ++ i){
        cin >> l[i] >> r[i];
        r[i] --; sr.pb(l[i]); sr.pb(r[i]);
    }
    sort(all(sr)); uq(sr); int sz = sr.size();

    for (int i = 0; i <= sz + 1; ++ i)
        for (int j = 0; j < LG; ++ j) to[i][j] = sz + 1;
    for (int i = 1; i <= n; ++ i){
        l[i] = fd(sr, l[i]) + 1;
        r[i] = fd(sr, r[i]) + 1;
        minl(to[l[i]][0], r[i]);
    }

    for (int i = sz; i >= 1; -- i){
        minl(to[i][0], to[i + 1][0]);
        for (int j = 1; j < LG; ++ j){
            int nxt = to[i][j - 1] + 1;
            if (nxt > sz) break;
            to[i][j] = to[nxt][j - 1];
        }
    }

    set <ii> s; s.insert({0, 0}); s.insert({sz + 1, sz + 1});

    vector <int> ans; int T = get(1, sz);
    if (T < k){
        cout << -1; return;
    }
    for (int i = 1; i <= n; ++ i){ if (ans.size() >= k) break;
        auto pl = *(--s.upper_bound({r[i], r[i]}));
        auto pr = *s.lower_bound({l[i], l[i]});
        if (pl.se >= l[i] || pr.fi <= r[i]) continue;
        int c = get(pl.se + 1, l[i] - 1) + get(r[i] + 1, pr.fi - 1) + 1 - get(pl.se + 1, pr.fi - 1);
        if (T + c >= k){
            T += c; ans.pb(i);
            s.insert({l[i], r[i]});
        }
    }

    for (int i : ans) cout << i << endl;
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

event2.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
event2.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
event2.cpp:20:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
event2.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
event2.cpp: In function 'void solve()':
event2.cpp:72:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     for (int i = 1; i <= n; ++ i){ if (ans.size() >= k) break;
      |                                        ~~~~~~~~~~~^~~~
event2.cpp: In function 'int main()':
event2.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
event2.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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