Submission #1037125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037125		hotboy2703	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	114 ms	42444 KiB

event2

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MAXN = 1e5+100;
const ll MAXK = 18;
ll sp[MAXK][MAXN*2];
pll a[MAXN];
pll b[MAXN];
ll n,k;
ll query(ll x,ll y){
    ll res = 0;
    for (ll j = MAXK-1;j >= 0;j --){
        if (sp[j][x] <= y){
            x=sp[j][x];
            res+=MASK(j);
        }
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>k;
    for (ll i = 1;i <= n;i ++)cin>>a[i].fi>>a[i].se;
    vector <ll> val;
    for (ll i = 1;i <= n;i ++){
        val.push_back(a[i].fi);
        val.push_back(a[i].se);
    }
    sort(val.begin(),val.end());
    val.resize(unique(val.begin(),val.end())-val.begin());
    for (ll i = 1;i <= n;i ++){
        a[i].fi = lower_bound(val.begin(),val.end(),a[i].fi) - val.begin();
        a[i].se = lower_bound(val.begin(),val.end(),a[i].se) - val.begin();
    }
    for (ll i = 1;i <= n;i ++)b[i] = a[i];
    sort(b+1,b+1+n,greater <> ());
    ll m = sz(val);
    sp[0][m] = m;
    for (ll i = m - 1,ptr = 1;i >= 0;i --){
        sp[0][i] = sp[0][i+1];
        while (ptr <= n && b[ptr].fi == i){
            sp[0][i] = min(sp[0][i],b[ptr].se);
            ptr++;
        }
    }
    for (ll j = 1;j < MAXK;j ++){
        for (ll i = 0;i <= m;i ++){
            sp[j][i] = sp[j-1][sp[j-1][i]];
        }
    }
    set <pll> s;
    s.insert(MP(0,0));
    s.insert(MP(m-1,m-1));
    ll pot = query(0,m-1);
    // cout<<pot<<endl;
    vector <ll> ans;
    for (ll i = 1;i <= n;i ++){
        if (sz(ans) < k){
            auto sus = s.insert(a[i]);
            if (sus.se==0)continue;
            auto tmp = sus.fi;
            if ((*prev(tmp)).se > a[i].fi || (*next(tmp)).fi < a[i].se)s.erase(a[i]);
            else{
                pot += -query((*prev(tmp)).se,(*next(tmp)).fi)
                        +query((*prev(tmp)).se,a[i].fi)
                        +query(a[i].se,(*next(tmp)).fi)
                        +1;
                if (pot < k){
                    pot -= -query((*prev(tmp)).se,(*next(tmp)).fi)
                        +query((*prev(tmp)).se,a[i].fi)
                        +query(a[i].se,(*next(tmp)).fi)
                        +1;
                    s.erase(a[i]);
                }
                else{
                    // cout<<i<<' '<<pot<<endl;
                    ans.push_back(i);
                }
            }
        }
    }
    if (sz(ans) < k)cout<<-1<<'\n';
    else for (auto x:ans)cout<<x<<'\n';
    return 0;
}

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