Submission #390804

#	Time	Username	Problem	Language	Result	Execution time	Memory
390804		couplefire	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	512 ms	18156 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 1000000009

int n, k, m;
array<int, 2> arr[MAXN];
vector<array<int, 2>> tmp;
vector<array<int, 2>> good;
set<array<int, 2>> st;
int dp[MAXN];
int fa[MAXN][20];

bool cmp(array<int, 2> a, array<int, 2> b){
    if(a[1] != b[1]) return a[1] < b[1];
    return a[0] < b[0];
}

int get(int l, int r){
    int p = lower_bound(good.begin(), good.end(), array<int, 2>{r, r}, cmp)-good.begin()-1;
    if(good[p][0] < l) return 0;
    int res = dp[p];
    for(int i = 19; i>=0; i--){
        if(good[fa[p][i]][0] >= l) p = fa[p][i];
    }
    p = lower_bound(good.begin(), good.end(), array<int, 2>{good[p][0], good[p][0]}, cmp)-good.begin()-1;
    return res - dp[p];
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    tmp.resize(n);
    for(int i = 0; i<n; i++){
        cin >> arr[i][0] >> arr[i][1];
        tmp[i] = arr[i];
    }
    sort(tmp.begin(), tmp.end(), [&](array<int, 2> a, array<int, 2> b){
        return a[1]-a[0] < b[1]-b[0];
    });
    for(auto p : tmp){
        auto it = st.lower_bound(p);
        if(it != st.end() && (*it)[1] <= p[1]) continue;
        good.push_back(p);
        st.insert(p);
    }
    sort(good.begin(), good.end());
    m = good.size();
    good.insert(good.begin(), {-2, -1});
    for(int i = 1; i<=m; i++){
        int pos = lower_bound(good.begin(), good.end(), array<int,2>{good[i][0], good[i][0]}, cmp)-good.begin()-1;
        dp[i] = 1+dp[pos];
        fa[i][0] = pos;
        for(int j = 1; j<20; j++) fa[i][j] = fa[fa[i][j-1]][j-1];
    }
    if(dp[m] < k){
        cout << -1 << endl;
        exit(0);
    }
    st.clear();
    st.insert({1, INF});
    int cnt = 0;
    int curans = dp[m];
    for(int i = 0; i<n; i++){
        if(cnt >= k) break;
        auto it = st.lower_bound(arr[i]);
        if(it == st.end() || (*it)[0] > arr[i][0]){
            if(it == st.begin()) continue;
            --it;
        }
        if((*it)[1] < arr[i][1]) continue;
        int l1 = (*it)[0], l2 = arr[i][0], r2 = arr[i][1], r1 = (*it)[1];
        int prvans = curans;
        curans -= get(l1, r1);
        curans += get(l1, l2); curans += get(r2, r1);
        curans++;
        if(curans >= k) cout << i+1 << endl, cnt++, st.erase(it), st.insert({l1, l2}), st.insert({r2, r1});
        else curans = prvans;
    }
}

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