Submission #972071

#	Time	Username	Problem	Language	Result	Execution time	Memory
972071		huutuan	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	166 ms	32204 KiB

event2

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10, LG=18;
int n, k;
int l[N], r[N];
vector<int> vv[N];
int jump[LG][N];

int get(int l, int r){
   int ans=0;
   for (int k=LG-1; k>=0; --k){
      if (jump[k][l]<=r){
         ans+=1<<k;
         l=jump[k][l];
      }
   }
   return ans;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> k;
   vector<int> vals{-1};
   for (int i=1; i<=n; ++i) cin >> l[i] >> r[i], vals.push_back(l[i]), vals.push_back(r[i]);
   sort(vals.begin(), vals.end()); vals.resize(unique(vals.begin(), vals.end())-vals.begin());
   for (int i=1; i<=n; ++i){
      l[i]=lower_bound(vals.begin(), vals.end(), l[i])-vals.begin();
      r[i]=lower_bound(vals.begin(), vals.end(), r[i])-vals.begin();
      vv[l[i]].push_back(r[i]);
   }
   int m=(int)vals.size()-1;
   jump[0][m+1]=m+1;
   for (int i=m; i>=1; --i){
      jump[0][i]=jump[0][i+1];
      for (auto &j:vv[i]) jump[0][i]=min(jump[0][i], j);
   }
   for (int k=1; k<LG; ++k) for (int i=1; i<=m+1; ++i) jump[k][i]=jump[k-1][jump[k-1][i]];
   set<pair<pair<int, int>, int>> st;
   st.insert({{1, m}, get(1, m)});
   int sum=st.begin()->second;
   if (sum<k){
      cout << -1 << '\n';
      return 0;
   }
   int tk=k;
   for (int i=1; i<=n && tk; ++i){
      auto it=st.lower_bound({{l[i], (int)1e9}, (int)1e9});
      if (it!=st.begin()){
         --it;
         int ll=it->first.first, rr=it->first.second;
         if (ll<=l[i] && r[i]<=rr){
            int tl=get(ll, l[i]);
            int tr=get(r[i], rr);
            if (sum-it->second+tl+tr+1>=k){
               sum=sum-it->second+tl+tr+1;
               st.erase(it);
               if (ll!=l[i]) st.insert({{ll, l[i]}, tl});
               if (r[i]!=rr) st.insert({{r[i], rr}, tr});
               cout << i << '\n';
               --tk;
            }
         }
      }
   }
   return 0;
}

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