Submission #725318

#	Time	Username	Problem	Language	Result	Execution time	Memory
725318		MohammadAghil	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	368 ms	42392 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)size(x)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pp;

void dbg(){
     cerr << endl;
}
template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          // freopen("inp.txt", "r", stdin);
          // freopen("out.txt", "w", stdout);
          #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
     #else
          #define er(...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 7, mod2 = 1e9 + 9, maxn = 2e5 + 5, lg = 21, inf = ll(1e9) + 5;

ll pw(ll a, ll b){
     if(b == 0) return 1;
     ll k = pw(a, b>>1);
     return k*k*(b&1ll?a:1);
}

vector<int> st[maxn], en[maxn];
int nxt[maxn][lg];
int suf[maxn];
pp p[maxn];

int get(int l, int r){
     if(p[suf[l]].ss > r) return 0;
     int cr = suf[l];
     int cnt = 1;
     per(i,lg-1,0){
          if(p[nxt[cr][i]].ss <= r){
               cr = nxt[cr][i];
               cnt += 1<<i;
          }
     }
     return cnt;
}

int main(){ IOS();  
     int n, k; cin >> n >> k;
     map<int, int> mp;
     rep(i,0,n){
          cin >> p[i].ff >> p[i].ss;
          mp[p[i].ff] = mp[p[i].ss] = 0;
     }
     int m = 0;
     for(auto&c: mp) c.ss = m++;
     p[n] = {m, m};
     rep(i,0,n){
          p[i] = {mp[p[i].ff], mp[p[i].ss]};
          st[p[i].ff].pb(i);
          en[p[i].ss].pb(i);
     }
     pp mn = {m, n};
     rep(i,0,lg) nxt[n][i] = n;
     per(i,m,0){
          for(int id: st[i]){
               mn = min(mn, {p[id].ss, id});
          }
          for(int id: en[i]){
               nxt[id][0] = mn.ss;
               rep(j,1,lg) nxt[id][j] = nxt[nxt[id][j-1]][j-1];
          }
     }
     suf[m] = n;
     per(i,m-1,0){
          suf[i] = suf[i+1];
          for(int id: st[i]){
               if(p[suf[i]].ss > p[id].ss){
                    suf[i] = id;
               }
          }
     }
     int cr = get(0, m-1);
     if(cr < k) return cout << -1 << '\n', 0;
     set<pp> s; 
     vector<int> ans;
     rep(i,0,n){
          int prv, nxt;
          auto it = s.lower_bound(pp(p[i].ss, -1));
          if(it == begin(s)) prv = 0;
          else{
               if(prev(it)->ss > p[i].ff) continue;
               prv = prev(it)->ss;
          }
          auto it2 = s.lower_bound(pp(p[i].ff, -1));
          if(it2 == end(s)) nxt = m-1;
          else{
               if(it2->ff < p[i].ss) continue;
               nxt = it2->ff;
          }
          int kp = cr - get(prv, nxt) + get(prv, p[i].ff) + get(p[i].ss, nxt) + 1;
          if(kp >= k){
               cr = kp;
               s.insert(p[i]);
               ans.pb(i);
          }
     }
     rep(i,0,k) cout << ans[i] + 1 << '\n';
     return 0;
}

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