제출 #659182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659182		zaneyu	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	99 ms	24520 KiB

event2

/*input
20 16
250732298 258217736
26470443 34965880
252620676 260043105
692063405 697656580
497457675 504191511
391372149 397942668
858168758 867389085
235756850 241022021
585764751 593366541
207824318 217052204
661682908 671226688
886273261 892279963
770109416 778960597
264372562 270395107
176883483 186662376
509929119 519063796
109491630 118520141
162731982 168101507
662727316 668317158
757072772 765493222
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<ll,ll>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET(v,x) lower_bound(ALL(v),x)-v.begin()
const int maxn=2e5+5;
const ll INF=0x3f3f3f3f;
const ld PI=acos(-1.0l);
const ld eps=1e-6;
const ll INF64=4e18+1;
const int MOD=1e9+7;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?"\n":"");
    return out;
}
inline ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
int l[maxn],r[maxn];
int suff[maxn];
int mn[maxn][20];
int get(int l,int r){
    int ans=0;
    for(int j=19;j>=0;j--){
        if(mn[l][j]<=r){
            l=mn[l][j];
            ans+=(1<<j);
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,k;
    cin>>n>>k;
    vector<pii> v;
    vector<int> dsc;
    REP(i,n){
        cin>>l[i]>>r[i];
        //--r[i];
        dsc.pb(l[i]),dsc.pb(r[i]);
    }
    SORT_UNIQUE(dsc);
    REP(i,2*n) suff[i]=INF;
    REP(i,n){
        l[i]=GET(dsc,l[i]),r[i]=GET(dsc,r[i]);
        MNTO(suff[l[i]],r[i]);
    }  
    for(int i=2*n-1;i>=0;i--) MNTO(suff[i],suff[i+1]);
    REP(i,2*n){
        mn[i][0]=suff[i];
    }
    REP1(j,19){
        REP(i,2*n){
            if(i+(1<<j)>2*n) break;
            if(mn[i][j-1]<INF) mn[i][j]=mn[mn[i][j-1]][j-1];
            else mn[i][j]=INF;
        }
    }
    set<pii> s;
    s.insert({0,0}),s.insert({2*n-1,2*n-1});
    vector<int> ans;
    REP(i,n){
        auto it=s.lower_bound({l[i],r[i]});
        if((it!=s.begin() and (*prev(it)).s>l[i]) or (it!=s.end() and ((*it).f)<r[i])){
            continue;
        }
        if(sz(s)+1+get((*prev(it)).s,l[i])+get(r[i],(*it).f)>=k){
            s.insert({l[i],r[i]});
            ans.pb(i+1);
        }
        if(sz(ans)==k) break;
    }
    if(sz(ans)!=k) cout<<-1;
    else cout<<ans;
}   

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