Submission #1144804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144804		antonn	Event Hopping 2 (JOI21_event2)	C++20	0 / 100	3079 ms	12948 KiB

event2

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; } 

const int N = 1e5 + 7;
const int L = 20;

int n, k;
vector<array<int, 3>> a;

int anc[L][N];

int get(int x, int l) {
    int ans = 0;
    for (int h = L - 1; h >= 0; --h) {
        if (anc[h][x] != 0 && a[anc[h][x]][2] <= l) {
            x = anc[h][x];
            ans += (1 << h);
        }
    }
    return ans;
}

set<array<int, 3>> s;

bool check(array<int, 3> x) {
    auto it = s.lower_bound({x[1], 0, 0});
    bool ok = 1;
    if (it != s.end()) {
        if ((*it)[0] >= x[1]) ok |= 1;
        else ok = 0;
    }
    if (it != s.begin()) {
        it = prev(it);
        if ((*it)[1] <= x[0]) ok |= 1;
        else ok = 0;
    }
    return ok;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> k;
    a.resize(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i][0] >> a[i][1]; 
    for (int i = 1; i <= n; ++i) a[i][2] = i;
     
    auto b = a;
    sort(b.begin() + 1, b.end());
    
    for (int i = 1; i <= n; ++i) {
        int l = i + 1, r = n, sol = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            if (b[i][0] >= a[i][1]) {
                sol = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        if (sol != 0) anc[0][i] = b[sol][2];
    }
    
    for (int h = 1; h < L; ++h) {
        for (int i = 1; i <= n; ++i) {
            anc[h][i] = anc[h - 1][anc[h - 1][i]];
        }
    }
    
    vector<int> sol;
    for (int i = 1; i <= n; ++i) {
        if (!check(a[i])) {
            continue;
        }
        s.insert(a[i]);
        vector<array<int, 3>> v;
        for (int j = 1; j <= n; ++j) {
            if (j != i && check(a[j])) {
                v.push_back(a[j]);
            }
        }
        sort(v.begin(), v.end());
        int ans = 0;
        int last = 0;
        for (auto x : v) {
            if (x[0] >= last) {
                last = x[1];
                ++ans;
            }
        }
        if (ans >= k - 1) {
            --k;
            sol.push_back(i);
        } else {
            s.erase(a[i]);
        }
        if (k == 0) break;
    }
    
    if ((int) sol.size() <= k) {
        cout << -1 << "\n";
        return 0;
    }
    for (auto i : sol) cout << i << "\n";
}

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