Submission #697429

#	Time	Username	Problem	Language	Result	Execution time	Memory
697429		urosk	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	455 ms	59876 KiB

event2

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}



#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);



using namespace std;
//using namespace __gnu_pbds;



#define maxn 200005
#define lg 21
ll n,m,k;
pll a[maxn];
pll b[maxn];
ll dp[maxn];
ll st[maxn][lg];
ll get(ll l,ll r){
    ll ans = 0;
    ll R = r;
    for(ll j = lg-1;j>=0;j--){
        if(st[R][j]>=l){
            ans+=(1<<j);
            R = st[R][j];
        }
    }
    return ans;
}
bool cmp(pll a,pll b){return a.sc<b.sc;}
int main(){
    daj_mi_malo_vremena
    cin >> n >> k;
    for(ll i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    {
        set<ll> s; map<ll,ll> mp;
        for(ll i = 1;i<=n;i++) s.insert(a[i].fi);
        for(ll i = 1;i<=n;i++) s.insert(a[i].sc);
        for(ll x : s) mp[x] = ++m;
        for(ll i = 1;i<=n;i++) a[i].fi = mp[a[i].fi];
        for(ll i = 1;i<=n;i++) a[i].sc = mp[a[i].sc];
    }
    m++;
    for(ll i = 1;i<=n;i++) b[i] = a[i];
    sort(b+1,b+1+n,cmp);
    ll j = 1,e = 0;
    for(ll i = 1;i<=m;i++){
        while(j<=n&&b[j].sc<=i){
            e = max(e,b[j].fi);
            j++;
        }
        if(j!=1) st[i][0] = e;
    }
    for(ll j = 1;j<lg;j++) for(ll i = 1;i<=m;i++) st[i][j] = st[st[i][j-1]][j-1];
    set<pll> s;
    s.insert({1,m});
    ll mx = get(1,m);
    vector<ll> ans;
    for(ll i = 1;i<=n;i++){
        ll l = a[i].fi,r = a[i].sc;
        auto it = s.upper_bound({r,r});
        if(it==s.begin()) continue;
        it--;
        ll L = (*it).fi,R = (*it).sc;
        if(!(l>=L&&r<=R)) continue;
        ll cur = mx + get(L,l) + get(r,R) - get(L,R) + 1;
        if(cur>=k){
            mx = cur;
            ans.pb(i);
            s.erase(it);
            s.insert({L,l});
            s.insert({r,R});
        }
    }
    if(sz(ans)<k){cout<<-1<<endl; return 0;}
    for(ll i = 0;i<k;i++) cout<<ans[i]<<endl;
    return 0;
}
/**
4 3
1 4
3 5
4 9
7 10



10 6
77412002 93858605
244306432 318243514
280338037 358494212
439397354 492065507
485779890 529132783
571714810 632053254
659767854 709114867
718405631 733610573
786950301 815106357
878719468 899999649
**/

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