Submission #398729

#	Time	Username	Problem	Language	Result	Execution time	Memory
398729		4fecta	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	1234 ms	62696 KiB

event2

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 200005, LOG = 19;

int n, k, bl[MN][LOG];
pii a[MN];
vector<int> xs, ls[MN];
map<int, int> mp;

int lift(int cur, int k) {
    for (int i = LOG - 1; i >= 0; i--) if (k - (1 << i) >= 0) cur = bl[cur][i], k -= 1 << i;
    return cur;
}

int count(int l, int r) {
    int lo = 0, hi = n, mid;
    while (lo < hi) {
        mid = (lo + hi + 1) >> 1;
        if (lift(r, mid) >= l) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

int32_t main() {
    boost();

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].f >> a[i].s;
        xs.push_back(a[i].f);
        xs.push_back(a[i].s);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for (int i = 0; i < xs.size(); i++) mp[xs[i]] = i + 1;
    for (int i = 1; i <= n; i++) a[i].f = mp[a[i].f], a[i].s = mp[a[i].s];
    for (int i = 1; i <= n; i++) ls[a[i].s].push_back(a[i].f);
    int mx = 0;
    for (int i = 1; i <= xs.size(); i++) {
        for (int p : ls[i]) mx = max(mx, p);
        bl[i][0] = mx;
        for (int j = 1; j < LOG; j++) bl[i][j] = bl[bl[i][j - 1]][j - 1];
    }
    set<pii> open;
    int cnt = count(1, xs.size());
    open.insert({1, xs.size()});
    vector<int> out;
    for (int i = 1; i <= n; i++) {
        if (out.size() == k) break;
        auto it = open.upper_bound({a[i].f, 0x3f3f3f3f});
        it--;
        pii cur = *it;
        if (a[i].f < cur.f || a[i].s > cur.s) continue;
        int tmp = count(cur.f, a[i].f) + count(a[i].s, cur.s) + 1 - count(cur.f, cur.s) + cnt;
        if (tmp >= k) {
            out.push_back(i);
            open.erase(cur);
            open.insert({cur.f, a[i].f});
            open.insert({a[i].s, cur.s});
            cnt = tmp;
        }
    }
    if (out.size() < k) printf("-1\n");
    else for (int p : out) printf("%lld\n", p);

    return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int32_t main()':
event2.cpp:45:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < xs.size(); i++) mp[xs[i]] = i + 1;
      |                     ~~^~~~~~~~~~~
event2.cpp:49:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 1; i <= xs.size(); i++) {
      |                     ~~^~~~~~~~~~~~
event2.cpp:59:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   59 |         if (out.size() == k) break;
      |             ~~~~~~~~~~~^~~~
event2.cpp:73:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   73 |     if (out.size() < k) printf("-1\n");
      |         ~~~~~~~~~~~^~~

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