Submission #947170

#	Time	Username	Problem	Language	Result	Execution time	Memory
947170		gesgha	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	135 ms	30320 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 = 2e5 + 10;
const int M = 3e3 + 10;
const int mod = 998244353;
const bool TEST = 0;

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




int dp[N];
int id_dp[N];
int mx_dp[N];


int mn[N][20];
int 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 <int, 3>> ev(n);
    ve <array <int, 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 += V[i][0] != V[i - 1][0];
            ev[V[i][1]][V[i][2]] = c;
        }
    }
    // for (int i = 0; i < n; i++) {
    //     cout << ev[i][0] << "\n";
    // }
    fill(go, go + 2 * n + 1, 2 * n);
    int mx = 0;
    for (int i = 0; i < n; i++) {
        umn(go[ev[i][0]], ev[i][1] + bool(ev[i][1] == ev[i][0]));
        umx(mx, ev[i][0]);
    }
    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 <int> L;
    set <int> R;
    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 = L.upper_bound(l);
            if (it != L.end()) ok &= (*it) >= r;
            if(it != L.begin()) {
                --it;
                ok &= (*it) < l;
            }
            it = R.upper_bound(l);
            if (it != R.end()) {
                ok &= (*it) > r;

            }
        }
        {
            auto to = R.upper_bound(l);
            if (to != R.end()) ok &= ((*to) >= r);
            if (to != R.begin()) {
                --to;
                lt = (*to);
            }
        }
        {
            auto to = L.lower_bound(r);
            if (to != L.begin()) {
                --to;
                ok &= ((*to) <= l);
                to++;
            }
            if (to != L.end()) {
                to--;
                rt = *to;
            }
        }
        if(!ok) continue;
        // cout << i << " " << lt << " " << rt << "\n";
        int was = get(lt, rt);
        int have = S - was + get(lt, l) + get(r, rt) + 1;
        // if(i == 0) cout << S - was << " " << k << "\n";
        if (have >= k) {
            S = have;
            L.insert(l);
            R.insert(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: 0 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61