Submission #593324

#	Time	Username	Problem	Language	Result	Execution time	Memory
593324		MohammadAghil	Event Hopping (BOI22_events)	C++17	30 / 100	246 ms	31760 KiB

events

#include <iostream>
#include <algorithm>
#include <functional>
#include <random>
#include <cmath>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <string>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <limits.h>
#include <tuple>
//   #pragma GCC optimization ("unroll-loops")
//  #pragma GCC optimization ("O3")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
  #define rep(i,l,r) for(int i = (l); i < (r); i++)
     #define all(x) begin(x), end(x)
        #define sz(x) (int)(x).size()
            #define pb push_back
                #define ss second
                     #define ff first
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 2e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

pp seg[maxn<<2];

void upd(int i, pp k, int x = 1, int lx = 0, int rx = maxn){
    if(lx + 1 == rx) {
        seg[x] = min(seg[x], k);
        return;
    }
    int mid = (lx + rx)>>1;
    if(i < mid) upd(i, k, x<<1, lx, mid);
    else upd(i, k, x<<1|1, mid, rx);
    seg[x] = min(seg[x<<1], seg[x<<1|1]);
}

pp get(int l, int r, int x = 1, int lx = 0, int rx = maxn){
    if(l <= lx && r >= rx) return seg[x];
    int mid = (lx + rx)>>1;
    pp res = {inf, inf};
    if(l < mid) res = get(l, r, x<<1, lx, mid);
    if(mid < r) res = min(res, get(l, r, x<<1|1, mid, rx));
    return res;
}

int nxt[maxn][lg];

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    int n, q; cin >> n >> q;
    rep(i,0,maxn<<2) seg[i] = {inf, inf};
    
    map<int, int> comp;
    vector<pp> trk(n);
    rep(i,0,n) cin >> trk[i].ss >> trk[i].ff, comp[trk[i].ff] = comp[trk[i].ss] = 0;
    vector<int> id(n), inv(n); iota(all(id), 0), sort(all(id), [&](int i, int j){ return trk[i] < trk[j]; });
    rep(i,0,n) inv[id[i]] = i;
    
    int dd = 0;
    for(auto&c:comp) c.ss = dd++;
    assert(dd < maxn);
    
    vector<vector<pp>> query(n);
    vector<int> ans(q, -1);
    rep(i,0,q){
        int l, r; cin >> l >> r; l--, r--;
        query[inv[r]].pb({inv[l], i});
    }
    auto chk = [&](int i, int j){
        return trk[id[j]].ss <= trk[id[i]].ff;
    };
    rep(i,0,n){
        auto[r, l] = trk[id[i]];
        upd(comp[r], {l, i});
        nxt[i][0] = get(comp[l], comp[r]+1).ss;
        rep(j,1,lg) nxt[i][j] = nxt[nxt[i][j-1]][j-1];
        assert(nxt[i][0] < n);
        for(auto[s, ID]: query[i]){
            if(s > i) continue;
            if(s == i) ans[ID] = 0;
            else{
                int cr = i;
                int res = 0;
                per(j,lg-1,0) if(!chk(s, nxt[cr][j])) cr = nxt[cr][j], res |= 1<<j;
                if(chk(s, nxt[cr][0])){
                    if(s == cr) ans[ID] = res;
                    else if(chk(s, cr)) ans[ID] = res + 1;
                    else ans[ID] = res + 2;
                }
            }
        }
    }
    rep(i,0,q){
        if(ans[i] == -1) cout << "impossible\n";
        else cout << ans[i] << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30