Submission #972977

#	Time	Username	Problem	Language	Result	Execution time	Memory
972977		Gajowy	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	151 ms	25544 KiB

event2

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define fwd(i, a, n) for (int i = (a); i < (n); i ++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) begin(X), end(X)
#define sz(X) ((int)X.size())
#define st first
#define nd second
#define vi vector<int>
#define pii pair<int, int>
#define ll long long
#define vll vector<long long>

#ifdef LOC
auto &operator<<(auto &out, pair<auto, auto> a) {
    return out << "(" << a.st << ", " << a.nd << ")";
}
auto &operator<<(auto &out, auto a) {
    out << "{";
    for (auto b : a)
        out << b << ", ";
    return out << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) 0
#endif

const int inf = 2e9;
const int LG = 20;

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, k;
    cin >> n >> k;
    vi l(n + 2), r(n + 2);
    vector<vi> jmp(LG, vi(n + 2));
    jmp[0][n + 1] = n + 1;
    l[n + 1] = inf;
    r[n + 1] = inf + 1;
    l[n] = -1;
    r[n] = 0;
    vector<array<int, 3> > a(n + 1);
    rep(i, n) {
        cin >> l[i] >> r[i];
        a[i] = {l[i], r[i], i};
    }
    a[n] = {l[n], r[n], n};
    sort(all(a), greater<array<int, 3> >());
    map<int, pii> dp;
    dp[l[n + 1]] = {r[n + 1], n + 1};
    for (auto [x, y, id] : a) {
        jmp[0][id] = dp.lower_bound(y)->nd.nd;
        dp[x] = min(make_pair(y, id), dp.lower_bound(x)->nd);
    }
    debug(jmp[0]);
    fwd(i, 1, LG)
        rep(j, n + 2)
            jmp[i][j] = jmp[i - 1][jmp[i - 1][j]];
    auto most = [&] (int v, int R) {
        int ans = 0;
        for (int i = LG - 1; i >= 0; i --)
            if (r[jmp[i][v]] <= R) {
                ans += (1 << i);
                v = jmp[i][v];
                debug(v);
            }
        return ans;
    };
    set<array<int, 3> > odp;
    odp.insert({l[n], r[n], n});
    odp.insert({l[n + 1], r[n + 1], n + 1});
    int S = most(n, inf - 1);
    if (S < k) {
        cout << "-1\n";
        return 0;
    }
    vi take(n, 0);
    rep(i, n) {
        auto nxt = odp.lower_bound({l[i], -1, -1});
        if ((*nxt)[0] < r[i]) continue;
        int R = (*nxt)[0];
        nxt --;
        if ((*nxt)[1] > l[i]) continue;
        int L = (*nxt)[1];
        int pid = (*nxt)[2];
        int will_have = S + most(pid, l[i]) + most(i, R) - most(pid, R);
        if (will_have < k - 1) continue;
        take[i] = 1;
        odp.insert({l[i], r[i], i});
        S = will_have;
        k --;
        if (k == 0) break;
    }
    rep(i, n)
        if (take[i])
            cout << i + 1 << "\n";
}

Compilation message (stderr)

event2.cpp: In function 'int32_t main()':
event2.cpp:29:20: warning: statement has no effect [-Wunused-value]
   29 | #define debug(...) 0
      |                    ^
event2.cpp:59:5: note: in expansion of macro 'debug'
   59 |     debug(jmp[0]);
      |     ^~~~~
event2.cpp: In lambda function:
event2.cpp:29:20: warning: statement has no effect [-Wunused-value]
   29 | #define debug(...) 0
      |                    ^
event2.cpp:69:17: note: in expansion of macro 'debug'
   69 |                 debug(v);
      |                 ^~~~~
event2.cpp: In function 'int32_t main()':
event2.cpp:88:13: warning: unused variable 'L' [-Wunused-variable]
   88 |         int L = (*nxt)[1];
      |             ^

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