Submission #1009441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009441		mispertion	Event Hopping (BOI22_events)	C++17	25 / 100	158 ms	80464 KiB

events

#include<bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
 
const ld PI = 3.1415926535;
const int N = 1e5+10;
const int M = 7e6 + 1;
int mod = 1e9 + 7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 467743;
 
int mult(int a, int b) {
    return a * 1LL * b % mod;
}
 
int sum(int a, int b) { 
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}
 
int binpow(int a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return mult(binpow(a, n - 1), a);
    } else {
        int b = binpow(a, n / 2);
        return mult(b, b);
    }
}

const int K = 20;
int n, st[N], en[N], up[N][K], q;
pii mnl[N];

struct sparset{
    pii st[N][K];
    
    void init(int n){
        for(int i = 1; i <= n; i++)
            st[i][0] = mnl[i];
        for(int k = 1; k < K; k++){
            for(int i = 1; i + (1 << k) - 1 <= n; i++)
                st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
        }
    }

    int get(int l, int r){
        int k = __lg(r - l + 1);
        return min(st[l][k], st[r - (1 << k) + 1][k]).S;
    }
};

void solve(){
    cin >> n >> q;
    vector<int> vs = {};
    for(int i = 1; i <= n; i++){
        cin >> st[i] >> en[i];
        vs.pb(st[i]);
        vs.pb(en[i]);
    }
    sort(all(vs));
    vs.resize(unique(all(vs)) - vs.begin());
    for(int i = 1; i <= sz(vs); i++){
        mnl[i] = {infl, 0};
    }
    for(int i = 1; i <= n; i++){
        int ps = upper_bound(all(vs), en[i]) - vs.begin();
        mnl[ps] = min(mnl[ps], {upper_bound(all(vs), st[i]) - vs.begin(), i});
    }
    sparset spr;
    spr.init(sz(vs));
    for(int i = 1; i <= n; i++){
        int l = upper_bound(all(vs), st[i]) - vs.begin(), r = upper_bound(all(vs), en[i]) - vs.begin();
        int ml = spr.get(l, r);
        up[i][0] = ml;
    }    
    for(int k = 1; k < K; k++)
        for(int i = 1; i <= n; i++)
            up[i][k] = up[up[i][k - 1]][k - 1];
    while (q--){
        int s, e;
        cin >> s >> e;
        if(s == e){
            cout << 0 << '\n';
            continue;
        }
        if(st[e] <= en[s] && en[s] <= en[e]){
            cout << 1 << '\n';
            continue;;
        }
        if(en[s] > en[e]){
            cout << "impossible\n";
            continue;
        }
        int sm = 0;
        for(int k = K - 1; k >= 0; k--){
            if(st[up[e][k]] > en[s]){
                e = up[e][k];
                sm += (1 << k);
            }
        }
        e = up[e][0];
        sm++;
        if(st[e] <= en[s] && en[s] <= en[e]){
            cout << 1 + sm << '\n';
        }else{
            cout << "impossible\n";
        }
    }
    
}
 
signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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