Submission #1264097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264097		hahahoang132	Event Hopping (BOI22_events)	C++20	20 / 100	111 ms	25928 KiB

events

//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const ll N = 1e5 + 5;
const ll inf = LLONG_MAX/5;
const ll mod = 998244353;
#define bit(x,y) ((x >> y) & 1LL)

struct haha
{
    ll s,e,id;
};
haha a[N];
ll nxt[22][N],pos[N],fm[N],lm[N];
ll cmp(haha x, haha y)
{
    return x.s < y.s;
}
struct segtree
{
    ll b[N * 4];
    ll c[N * 4];
    ll n;
    void build(ll n)
    {
        this->n = n;
        build(0,1,n);
    }
    void build(ll x, ll l, ll r)
    {
        if(l == r)
        {
            b[x] = a[l].e;
            c[x] = l;
        }else
        {
            ll mid = (l + r) / 2;
            build(x * 2 + 1,l,mid);
            build(x * 2 + 2,mid + 1,r);
            if(b[x * 2 + 1] >= b[x * 2 + 2])
            {
                b[x] = b[x * 2 + 1];
                c[x] = c[x * 2 + 1];
            }else
            {
                b[x] = b[x * 2 + 2];
                c[x] = c[x * 2 + 2];
            }
        }
    }
    ll maxv(ll l, ll r)
    {
        return maxv(0,1,n,l,r).second;
    }
    pair<ll,ll> maxv(ll x, ll l, ll r, ll s, ll e)
    {
        if(r < s || e < l) return {-inf,-1};
        if(s <= l && r <= e) return {b[x],c[x]};
        ll mid = (l + r) / 2;
        pair<ll,ll> t1 = maxv(x * 2 + 1,l,mid,s,e);
        pair<ll,ll> t2 = maxv(x * 2 + 2,mid + 1,r,s,e);
        if(t1.first >= t2.first)
        {
            return t1;
        }else return t2;
    }
};
segtree f;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,q;
    cin >> n >> q;
    ll i,j;
    for(i = 1;i <= n;i++)
    {
        cin >> a[i].e >> a[i].s;
        a[i].e = -a[i].e;
        a[i].s = -a[i].s;
        a[i].id = i;
    }
    sort(a + 1,a + 1 + n,cmp);
    ll maxv = -inf;
    for(i = 1;i <= n;i++)
    {
        pos[a[i].id] = i;
    }
    f.build(n);
    ll tmp = 0;
    for(i = 1;i <= n;i++)
    {
        if(i == 1) tmp = 1;
        else
        {
            if(a[i].s != a[tmp].s) tmp = i;
        }
        ll l = 1,r = n;
        while(l < r)
        {
            ll mid = (l + r + 1) / 2;
            if(a[mid].s <= a[i].e) l = mid;
            else r = mid - 1;
        }
        nxt[0][i] = f.maxv(tmp,l);
        lm[i] = l;
    }
    for(i = 1;i <= 20;i++)
    {
        for(j = 1;j <= n;j++) nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
    }
    while(q--)
    {
        ll x,y;
        cin >> y >> x;
        x = pos[x];
        y = pos[y];
        if(x >= y)
        {
            if(x == y) cout << 0;
            else cout << "impossible";
        }else
        {
            ll ans = 0;
            for(i = 20;i >= 0;i--)
            {
                if(lm[nxt[i][x]] < y)
                {
                    ans += (1LL << i);
                    x = nxt[i][x];
                }
            }
            if(lm[x] >= y)
            {
                cout << ans + 1;
            }else
            {
                if(lm[nxt[0][x]] >= y) cout << ans + 2;
                else cout << "impossible";
            }
        }
        cout << "\n";
    }
}

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