Submission #1042172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042172		KiaRez	Event Hopping (BOI22_events)	C++17	100 / 100	603 ms	49872 KiB

events

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 17;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, q, rev[N], p[N], s[N], e[N], a[N];
pii seg[lg][N], cte=Mp((int)1e9, (int)-1e9);

bool cmp(int i, int j) {
    return (e[i] < e[j]);
}

void upd(int id, int ind, pii x) {
    while(ind > 0) {
        seg[id][ind].F=min(seg[id][ind].F, x.F);
        seg[id][ind].S=max(seg[id][ind].S, x.S);
        ind /= 2;
    }
}

pii query(int l, int r, int id, int ind=1, int lc=1, int rc=(1<<lg)+1) {
    if(l >= rc || lc >= r) return cte;
    if(lc >= l && rc <= r) return seg[id][ind];
    int mid = (lc + rc)/2;
    pii x = query(l, r, id, 2*ind, lc, mid);
    pii y = query(l, r, id, 2*ind+1, mid, rc);
    return Mp(min(x.F, y.F), max(x.S, y.S));
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>q;
    for(int i=1; i<=n; i++) {
        cin>>s[i]>>e[i]; p[i] = i;
    }
    sort(p+1, p+n+1, cmp);
    for(int i=1; i<=n; i++) rev[p[i]] = i, a[i] = e[p[i]];
    a[n+1] = 2e9;

    for(int i=0; i<lg; i++) fill(seg[i], seg[i]+N, cte);
    for(int i=1; i<=n; i++) {
        int pl=lower_bound(a+1, a+n+2, s[p[i]]) - a;
        int pr=upper_bound(a+1, a+n+2, e[p[i]]) - a - 1;
        // cout<<p[i]<<" ==> "<<pl<<' '<<pr<<endl;
        upd(0, (1<<lg)-1+i, Mp(pl, pr));
    }

    for(int i=1; i<lg; i++) {
        for(int j=1; j<=n; j++) {
            pii tmp = seg[i-1][(1<<lg)-1+j];
            pii res = query(tmp.F, tmp.S+1, i-1);
            upd(i, (1<<lg)-1+j, res);
        }
    }

    for(int v,u,tc=1; tc<=q; tc++) {
        cin>>v>>u;
        if(v == u) {
            cout<<0<<endl; continue;
        }
        v=rev[v], u=rev[u];
        pii now = {u, u}; int ans = 0;
        for(int i=lg-1; i>=0; i--) {
            pii tmp = query(now.F, now.S+1, i);
            if(v < tmp.F || v > tmp.S) {
                ans += (1<<i);
                now = tmp;
            }
        }
        if(ans == (1<<lg) - 1) {
            cout<<"impossible\n"; continue;
        } 
        cout<<ans+1<<endl;
    }

	return 0;
}

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