Submission #714375

#	Time	Username	Problem	Language	Result	Execution time	Memory
714375		ibrahim001	Event Hopping (BOI22_events)	C++14	100 / 100	644 ms	23652 KiB

events

#include "bits/stdc++.h"
#define intt long long
#define pb push_back
#define endl '\n'
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<intt,intt>
#define ld long double
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int sz = 2e5+5;
const int inf = 1e9+7;
int a[sz], b[sz];
map<int,int> mp;
pii st[sz<<2];
int par[sz][20];
void build(int l, int r, int in){
    st[in]={inf, inf};
    if ( l == r ){
        return;
    }
    int mid = (l+r)>>1;
    build(l, mid, in<<1);
    build(mid+1, r, in<<1|1);
}
void update(int l, int r, int in, int x, int val){
    if ( x > r or x < l )   return;
    if ( l == r ){
        st[in] = min(st[in], {a[val], val});
        return;
    }
    int mid = (l+r)>>1;
    update(l, mid, in<<1, x, val);
    update(mid+1, r, in<<1|1, x, val);
    st[in] = min(st[in<<1], st[in<<1|1]);
}
pii getans(int a, int b, int l, int r, int in){
    if ( l > b or r < a )   return {inf, inf};
    if ( a <= l and r <= b )    return st[in];
    int mid = (l+r)>>1;
    return min(getans(a, b, l, mid, in<<1), getans(a, b, mid+1, r, in<<1|1));
}
int i,j;
int main(){
    int n, q;
    cin >> n >> q;
    for ( i = 1; i <= n; i++ ){
        cin >> a[i] >> b[i];
        mp[a[i]];
        mp[b[i]];
    }
    int cnt = 0;
    for ( pii i : mp ){
        mp[i.F] = ++cnt;
    }
    build(1, n*2, 1);
    for ( i = 1; i <= n; i++ ){
        a[i] = mp[a[i]];
        b[i] = mp[b[i]];
        update(1, n*2, 1, b[i], i);
    }
    for ( i = 1; i <= n; i++ ){
        par[i][0] = getans(a[i], b[i], 1, n*2, 1).S;
        if ( par[i][0] == i )    par[i][0] = 0;
    }
    for ( i = 1; i < 20; i++ ){
        for ( j = 1; j <= n; j++ )  par[j][i] = par[par[j][i-1]][i-1];
    }
    while(q--){
        int x, y;
        cin >> x >> y;
        if ( x == y ){
            cout << 0 << endl;
            continue;
        }
        if ( b[x] > b[y] ){
            cout << "impossible" << endl;
            continue;
        }
        if ( b[x] >= a[y] and b[x] <= b[y] ){
            cout << 1 << endl;
            continue;
        }
        int res = 0;
        for ( i = 19; i >= 0; i-- ){
            if ( a[par[y][i]] > b[x] ){
                y = par[y][i];
                res+=(1<<i);
            }
        }
        y = par[y][0];
        res++;
        if ( y == 0 ){
            cout << "impossible" << endl;
            continue;
        }
        cout << res+1 << endl;
    }
}

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