Submission #875586

#	Time	Username	Problem	Language	Result	Execution time	Memory
875586		vjudge1	Event Hopping 2 (JOI21_event2)	C++17	7 / 100	146 ms	33232 KiB

event2

// https://oj.uz/problem/view/JOI21_event2

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 1e8;

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

        int n, k;
        cin >> n >> k;
        vector<int> l(n), r(n);
        for (int i = 0; i < n; i++) cin >> l[i] >> r[i];
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);

        // calc nxt

        sort(ord.begin(), ord.end(), [&](int i, int j) {
                return l[i] < l[j];
        });
        vector<int> suff(n);
        suff.back() = ord.back();
        for (int i = n - 1; i > 0; i--) suff[i - 1] = r[ord[i - 1]] < r[suff[i]] ? ord[i - 1] : suff[i];
        auto sl = l;
        vector<vector<int>> nxt(__lg(n) + 1, vector<int>(n + 1, n));
        sort(sl.begin(), sl.end());
        for (int i = 0; i < n; i++) {
                int j = lower_bound(sl.begin(), sl.end(), r[i]) - sl.begin();
                if (j == n) {
                        nxt[0][i] = n;
                } else {
                        nxt[0][i] = suff[j];
                }
        }

        // calc prv

        sort(ord.begin(), ord.end(), [&](int i, int j) {
                return r[i] < r[j];
        });
        vector<int> pref(n);
        pref[0] = ord[0];
        for (int i = 1; i < n; i++) pref[i] = l[ord[i]] > l[pref[i - 1]] ? ord[i] : pref[i - 1];
        auto sr = r;
        vector<vector<int>> prv(__lg(n) + 1, vector<int>(n + 1, n));
        sort(sr.begin(), sr.end());
        for (int i = 0; i < n; i++) {
                int j = upper_bound(sr.begin(), sr.end(), l[i]) - sr.begin() - 1;
                if (j == -1) {
                        prv[0][i] = n;
                } else {
                        prv[0][i] = pref[j];
                }
        }

        for (int i = 1; i <= __lg(n); i++) {
                for (int j = 0; j < n; j++) {
                        nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
                        prv[i][j] = prv[i - 1][prv[i - 1][j]];
                }
        }

        vector<int> cnt_left(n), cnt_right(n);
        int cnt_all = 0;

        auto try_first = [&](int x) {
                int cnt = 1;
                int l = x, r = x;
                for (int i = __lg(n); i >= 0; i--) {
                        if (nxt[i][r] != n) r = nxt[i][r], cnt += 1 << i, cnt_right[x] += 1 << i;
                        if (prv[i][l] != n) l = prv[i][l], cnt += 1 << i, cnt_left[x] += 1 << i;
                }
                return cnt >= k;
        };

        vector<int> ans;

        set<int> s, set_left, set_right;
        set<pair<int, int>> set_point;

        auto intersect = [&](int x) {
                auto ll = set_left.upper_bound(l[x]);
                auto lr = set_right.upper_bound(l[x]);
                int pos_left, pos_right;
                if (ll == set_left.begin()) {
                        pos_left = -inf - 1;
                } else {
                        pos_left = *prev(ll);
                }
                if (lr == set_right.begin()) {
                        pos_right = -inf + 1;
                } else {
                        pos_right = *prev(lr);
                }
                if (pos_right <= pos_left) return 1;
                auto rl = set_left.lower_bound(r[x]);
                auto rr = set_right.lower_bound(r[x]);
                if (rl == set_left.end()) {
                        pos_left = inf - 1;
                } else {
                        pos_left = *rl;
                }
                if (rr == set_right.end()) {
                        pos_right = inf + 1;
                } else {
                        pos_right = *rr;
                }
                if (pos_left >= pos_right) return 1;
                return 0;
        };

        auto try_add = [&](int x) {
                auto L = set_right.upper_bound(l[x]);
                auto R = set_left.lower_bound(r[x]);
                int limit_left, limit_right;
                if (L == set_right.begin()) {
                        limit_left = -inf;
                } else {
                        limit_left = *prev(L);
                }
                if (R == set_left.end()) {
                        limit_right = +inf;
                } else {
                        limit_right = *R;
                }

                auto right_it = set_point.lower_bound(make_pair(l[x], +inf));
                int cur = right_it == set_point.end() ? cnt_right[(prev(right_it))->second] : cnt_left[right_it->second];
                int le = x, ri = x;
                cnt_left[x] = cnt_right[x] = 0;
                for (int i = __lg(n); i >= 0; i--) {
                        if (nxt[i][ri] != n && r[nxt[i][ri]] <= limit_right) {
                                ri = nxt[i][ri];
                                cnt_right[x] += 1 << i;
                        }
                        if (prv[i][le] != n && l[prv[i][le]] >= limit_left) {
                                le = prv[i][le];
                                cnt_left[x] += 1 << i;
                        }
                }
                if (cnt_all + cnt_left[x] + cnt_right[x] + 1 - cur < k) return 0;
                cnt_all -= cur;
                cnt_all += cnt_left[x] + cnt_right[x] + 1;
                if (right_it != set_point.begin()) {
                        auto left_it = prev(right_it);
                        cnt_right[left_it->second] = cnt_left[x];
                }
                if (right_it != set_point.end()) {
                        cnt_left[right_it->second] = cnt_right[x];
                }
                return 1;
        };

        for (int i = 0; i < n; i++) {
                if (try_first(i)) {
                        ans.emplace_back(i);
                        set_left.emplace(l[i]), set_right.emplace(r[i]);
                        set_point.emplace(l[i], i);
                        cnt_all = cnt_left[i] + cnt_right[i] + 1;
                        break;
                }
        }

        if (ans.size() == 0) return cout << -1, 0;

        for (int i = 0; i < n; i++) {
                if (intersect(i)) continue;
                if (try_add(i) && set_point.size() < k) {
                        ans.emplace_back(i);
                        set_left.emplace(l[i]);
                        set_right.emplace(r[i]);
                        set_point.emplace(l[i], i);
                }
        }

        for (int i : ans) cout << i + 1 << '\n';
}

Compilation message (stderr)

event2.cpp: In function 'int32_t main()':
event2.cpp:171:52: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  171 |                 if (try_add(i) && set_point.size() < k) {
      |                                   ~~~~~~~~~~~~~~~~~^~~

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