Submission #947198

#	Time	Username	Problem	Language	Result	Execution time	Memory
947198		gesgha	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	135 ms	53432 KiB

event2

#include <bits/stdc++.h>
// #pragma GCC target("popcnt")

#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back

#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
using ve = vector <T>;

template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }

template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }

using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using ull = unsigned long long;

const int oo = 1e9 + 100;
const ll OO = 1e18;
const int N = 5e5 + 10;
const int M = 3e3 + 10;
const int mod = 998244353;
const bool TEST = 0;

mt19937_64 rng(228);
void precalc() {}




ll mn[N][20];
ll go[N];

int get(int l, int r) {
    int S = 0;
    for (int i = 19; i >= 0; i--) if (mn[l][i] <= r) {
        S += pw(i);
        l = mn[l][i];
    }
    return S;
}

void slv() {
    int n, k;
    cin >> n >> k;
    ve <array <ll, 3>> ev(n);
    ve <array <ll, 3>> V;
    
    for (int i = 0; i < n; i++) {
        cin >> ev[i][0] >> ev[i][1];
        V.pb({ev[i][0], i, 0});
        V.pb({ev[i][1], i, 1});
    }
    int c = 0;
    {
        sort(all(V));
        ev[V[0][1]][V[0][2]] = c;
        for (int i = 1; i < sz(V); i++) {
            c += bool(V[i][0] != V[i - 1][0]);
            ev[V[i][1]][V[i][2]] = c;
        }   
    }
    
    fill(go, go + 2 * n + 2, 2 * n);
    for (int i = 0; i < n; i++) {
        umn(go[ev[i][0]], ev[i][1]);
    }
    for (int i = 2 * n - 1; i >= 0; i--) umn(go[i], go[i + 1]);
    for (int i = 0; i < 20; i++) mn[2 * n][i] = 2 * n;
    for (int i = 2*n - 1; i >= 0; i--) {
        mn[i][0] = go[i];
        for (int st = 1; st < 20; st++) mn[i][st] = mn[mn[i][st - 1]][st - 1];
    }
    set <pii> Seg;
    int S = get(0, 2 * n - 1);
    if (S < k) {
        cout << "-1\n";
        exit(0);
    }
    ve <int> ans;
    for (int i = 0; i < n; i++) {
        int l = ev[i][0];
        int r = ev[i][1];
        int lt = 0, rt = 2 * n - 1;
        bool ok = 1;
        {
            auto it = Seg.lower_bound({l, -oo});
            if (it != Seg.end()) {
                ok &= ((*it).fi >= r);
                rt = (*it).fi;
            }
            if (it != Seg.begin()) {
                --it;
                lt = (*it).se;
                ok &= ((*it).se <= l);
            }
            
        }
        if(!ok) continue;
        int was = get(lt, rt);
        int have = S - was + get(lt, l) + get(r, rt) + 1;
        if (have >= k) {
            S = have;
            Seg.insert({l, r});
            ans.pb(i);
        }
        if (sz(ans) == k) break;
    }
    fe(x, ans) {
        cout << x + 1 << '\n';
    }

}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    precalc();
    cout << fixed << setprecision(13);
    int q = 1;
    if (TEST) cin >> q;
    while (q--) slv();
    return 0;
}

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