Submission #1144821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144821		antonn	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	136 ms	18112 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) {
    if (a[x][1] > l) return 0;
    int ans = 0;
    for (int h = L - 1; h >= 0; --h) {
        if (anc[h][x] != 0 && a[anc[h][x]][1] <= l) {
            x = anc[h][x];
            ans += (1 << h);
        }
    }
    return ans + 1;
}

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 mn = -1, still = 0;

void baga(array<int, 3> x) {
    auto it = s.lower_bound({x[1], 0, 0});
    if (it == s.end()) {
        if (it == s.begin()) {
            still -= get(mn, 2e9);
            still += get(mn, x[0]);
            still += get(x[2], 2e9) - 1;
        } else {
            auto it2 = prev(it);
            still -= get((*it2)[2], 2e9) - 1;
            still += get((*it2)[2], x[0]) - 1;
            still += get(x[2], 2e9) - 1;
        }
    } else {
        if (it == s.begin()) {
            still -= get(mn, (*it)[0]);
            still += get(mn, x[0]);
            still += get(x[2], (*it)[0]) - 1;
        } else {
            auto it2 = prev(it);
            still -= get((*it2)[2], (*it)[0]) - 1;
            still += get((*it2)[2], x[0]) - 1;
            still += get(x[2], (*it)[0]) - 1;
        }
    }
    s.insert(x);
}

void scoate(array<int, 3> x) {
    auto it = s.find(x);
    if (it == prev(s.end())) {
        if (it == s.begin()) {
            still -= get(mn, (*it)[0]);
            still -= get((*it)[2], 2e9) - 1;
            still += get(mn, 2e9);
        } else {
            auto it2 = prev(it);
            still -= get((*it2)[2], (*it)[0]) - 1;
            still -= get((*it)[2], 2e9) - 1; 
            still += get((*it2)[2], 2e9) - 1;
        }
    } else {
        if (it == s.begin()) {
            still -= get(mn, (*it)[0]);
            still -= get((*it)[2], (*next(it))[0]) - 1;
            still += get(mn, (*next(it))[0]);
        } else {
            still -= get((*prev(it))[2], (*it)[0]) - 1;
            still -= get((*it)[2], (*next(it))[0]) - 1;
            still += get((*prev(it))[2], (*next(it))[0]) - 1;
        }
    }
    s.erase(it);
}

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(), [&](array<int, 3> a, array<int, 3> b) {
        if (a[1] == b[1]) return a[0] < b[0];
        return a[1] < b[1];
    });
    
    vector<int> pref(n + 1);
    for (int i = 1; i <= n; ++i) pref[i] = max(pref[i - 1], b[i][0]);
    
    for (int i = 1; i <= n; ++i) {
        int l = 1, r = n, sol = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            if (pref[m] >= 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]];
        }
    }
    
    for (int i = 1; i <= n; ++i) if (mn == -1 || a[i][1] < a[mn][1] || (a[i][1] == a[mn][1] && a[i][0] < a[mn][0])) mn = i;
    still = get(mn, 2e9);
    
    vector<int> sol;
    for (int i = 1; i <= n; ++i) {
        if (!check(a[i])) {
            continue;
        }
        baga(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(), [&](array<int, 3> a, array<int, 3> b) {
            //if (a[1] == b[1]) return a[0] < b[0];
            //return a[1] < b[1];
        //});
        
        //int brut = 0;
        //int last = 0;
        //for (auto x : v) {
            //if (x[0] >= last) {
                //last = x[1];
                //++brut;
            //}
        //}
        //cout << "!" << i << " a " << still << ": " << brut << "\n";
        // assert(still == brut);
        
        if (still >= k - 1) {
            --k;
            sol.push_back(i);
        } else {
            scoate(a[i]);
        }
        if (k == 0) break;
    }
    
    if (k != 0) {
        cout << -1 << "\n";
        return 0;
    }
    for (auto i : sol) cout << i << "\n";
}

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