Submission #1135899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135899		Psiuk_Yurii	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	310 ms	60336 KiB

event2

#include <bits/stdc++.h>

using namespace std;
/*
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppl;

struct S{
  ll L,R,x;
};
S a[100009];
ll n,k,dp[100009][25],h,r[100009],mod,c;
struct Tree{
   pll T[800009];
   void init(){
     for(int i=0;i<=4*c;i++) T[i]={c,2};
   }
   void add(int v,int tl,int tr,int t){
        if(T[v].first>a[t].R){
            T[v]={a[t].R,a[t].x};
        }
        if(tl==tr) return;
        int tm=(tl+tr)>>1;
        if(a[t].L<=tm) add(2*v+1,tl,tm,t);
        else add(2*v+2,tm+1,tr,t);
   }
   pll get(int v,int tl,int tr,int R){
       //cout<<v<<" "<<tl<<" "<<tr<<" "<<R<<" "<<T[v].first<<" "<<T[v].second<<endl;
      if(R<=tl) return T[v];
      if(tr<R) return {c,2};
      int tm=(tl+tr)>>1;
      pll G=get(2*v+1,tl,tm,R);
      pll H=get(2*v+2,tm+1,tr,R);
      if(G.first<=H.first) return G;
      else return H;
   }
   void add(int t){
      add(0,1,c,t);
   }
   pll get(int R){
      // cout<<"? "<<R<<endl;
      return get(0,1,c,R);
   }
};
Tree D;


bool cmp(S w,S u){
    if(w.L!=u.L) return w.L<u.L;
    if(w.R!=u.R) return w.R<u.R;
    return w.x>u.x;
}
vector<ll> B;
map<ll,ll> mp;
ll res;
set<ppl> s;
ll f(){
   ll o=0;
   ll v=1;
   while(1){
      o++;
      if(v==2) break;
      v=dp[v][0];
   }
   return o;
}
ll f(ll tL,ll tR){
   ll sum=0;
   ll v=tL;
   if(tR==2){
       for(int i=h;i>=0;i--){
             if(a[r[dp[v][i]]].R<=a[r[tR]].L && dp[v][i]!=2) {
             sum+=(1LL<<i);
             v=dp[v][i];
        }
        }
        return sum;
   }
   for(int i=h;i>=0;i--){
      if(a[r[dp[v][i]]].R<=a[r[tR]].L) {
        sum+=(1LL<<i);
        v=dp[v][i];
      }
   }
   return sum;
}
set<ll> ans;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    mod=1e9+7;
    h=22;
    cin>>n>>k;
    n+=2; k+=2;
    a[1]={0,0,1};
    B.push_back(0);
    a[2]={mod,mod,2};
    B.push_back(mod);
    for(int i=3;i<=n;i++) {cin>>a[i].L>>a[i].R; B.push_back(a[i].L); B.push_back(a[i].R); a[i].x=i;}
    sort(B.begin(),B.end());
    for(auto x:B){
        c++;
        mp[x]=c;
    }
    for(int i=1;i<=n;i++){
        a[i].R=mp[a[i].R];
        a[i].L=mp[a[i].L];
    }
    sort(a+1,a+n+1,cmp);
   /* for(int i=1;i<=n;i++) {
        cout<<a[i].L<<" "<<a[i].R<<" "<<a[i].x<<endl;
    }*/
    for(int i=1;i<=n;i++) r[a[i].x]=i;
    for(int i=0;i<=h;i++) dp[2][i]=2;

    D.init();
    D.add(n);
    for(int i=n-1;i>=1;i--){
        dp[a[i].x][0]=D.get(a[i].R).second;
        D.add(i);
        for(int j=1;j<=h;j++) dp[a[i].x][j]=dp[dp[a[i].x][j-1]][j-1];
    }
    //for(int i=1;i<=n;i++) cout<<i<<" "<<dp[i][0]<<endl;
    //cout<<f(1,2)<<endl;

    s.insert({{a[1].L,a[1].R},a[1].x});
    s.insert({{a[n].L,a[n].R},a[n].x});
    res=f();
    if(res<k) {
        cout<<"-1\n";
        return 0;
    }
    for(int i=3;i<=n;i++){
        auto id=s.lower_bound({{a[r[i]].R,a[r[i]].R},0});
        auto id2=prev(id);
        ppl G=*id;
        ppl H=*id2;
        if(a[r[H.second]].R>a[r[i]].L || a[r[G.second]].L<a[r[i]].R) continue;
        ll P=res-f(H.second,G.second)+f(H.second,i)+f(i,G.second)+1;
        if(P>=k) {
            res=P;
            s.insert({{a[r[i]].L,a[r[i]].R},a[r[i]].x});
            if(s.size()==k) break;
        }
    }
    for(auto x:s) ans.insert(x.second-2);
    for(auto x:ans) if(x>0) cout<<x<<"\n";





    return 0;
}

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