Submission #915716

#	Time	Username	Problem	Language	Result	Execution time	Memory
915716		LOLOLO	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	195 ms	42072 KiB

event2

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

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 3e5 + 10;
int sp[N][20], mi[N];

int get(int l, int r) {
    int ans = 0;
    for (int i = 19; i >= 0; i--) {
        if (sp[l][i] <= r) {
            l = sp[l][i];
            ans += (1 << i);
        }
    }

    return ans;
}

int solve() {
    mem(sp, 0x3f);
    mem(mi, 0x3f);

    int n, k;
    cin >> n >> k;

    map <int, int> mp;
    int timer = 1;

    vector <pair <int, int>> save(n);
    for (auto &x : save) {
        cin >> x.f >> x.s;
        mp[x.f], mp[x.s];
    }

    for (auto &x : mp)
        x.s = timer++;

    for (auto &x : save) {
        x.f = mp[x.f], x.s = mp[x.s];
        mi[x.f] = min(mi[x.f], x.s);
    }

    mi[timer + 1] = timer + 1;
    for (int i = timer + 1; i >= 0; i--) {
        mi[i] = min(mi[i], mi[i + 1]);
        sp[i][0] = mi[i];
    }

    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= timer + 1; i++) {
            sp[i][j] = sp[sp[i][j - 1]][j - 1];
        }
    }

    if (get(1, timer) < k) {
        cout << -1 << '\n';
        return 0;
    }

    set <pair <int, int>> seg;
    seg.insert(make_pair(1, timer));
    int all = get(1, timer), cnt = k;

    for (int i = 0; i < n; i++) {
        if (cnt == 0)
            break;

        int l = save[i].f, r = save[i].s;
        auto it = seg.lower_bound({l, r});

        if (it == seg.end() || (it -> f > l && it != seg.begin())) {
            --it;
        }

        int l1 = it -> f, r1 = it -> s;

        if (l1 <= l && r1 >= r) {
            int nw = 1 + get(l1, l) + get(r, r1) + all - get(l1, r1);
            if (nw >= k) {
                cout << i + 1 << '\n';
                cnt--;
                seg.erase(it);
                seg.insert({l1, l});
                seg.insert({r, r1});
                all = nw;
            }
        }
    }

    return 0;
}

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

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
        //cout << solve() << '\n';
    }

    return 0;
}

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