제출 #588926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588926		ParsaEs	Event Hopping (BOI22_events)	C++17	0 / 100	1548 ms	4104 KiB

events

//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("unroll-loops", "Ofast", "O3")
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, l, r) for(ll i = l; i < r; i++)
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
#define X first
#define Y second
typedef int ll;
using namespace std;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pi;
constexpr ll inf = 2e9, xn = 1e5 + 5, s = 317;
ll d[xn], p[xn], sx[xn], x[xn], m[s];
pi e[xn];
int main()
{
    Fast
    ll n, q;
    cin >> n >> q;
    rep(i, 0, n) cin >> e[i].Y.X >> e[i].X;
    rep(i, 0, n) e[i] = {-e[i].X, {-e[i].Y.X, i}};
    sort(e, e + n);
    rep(i, 0, s) m[i] = -inf;
    rep(i, 0, n)
    {
        sx[i] = x[i] = -1;
        rep(j, 0, i / s + 1) if(e[i].X <= m[j])
        {
            rep(k, j * s, min((j + 1) * s, i)) if(e[i].X <= e[k].Y.X)
            {
                if(k / s < i / s) sx[i] = k, d[i] = 1;
                else if(sx[k] >= 0) sx[i] = sx[k], d[i] = d[k] + 1;
                x[i] = k;
                break;
            }
            break;
        }
        m[i / s] = max(e[i].Y.X, m[i / s]), p[e[i].Y.Y] = i;
    }
    while(q--)
    {
        ll l, r, ans = 0;
        cin >> l >> r;
        if(l == r)
        {
            cout << "0\n";
            continue;
        }
        l = p[l - 1], r = p[r - 1];
        if(e[l].X < e[r].X)
        {
            cout << "impossible\n";
            continue;
        }
        if(e[l].X == e[r].X)
        {
            cout << "1\n";
            continue;
        }
        ll y = l;
        while(sx[y] >= r) ans += d[y], y = sx[y];
        while(x[y] >= r) y = x[y], ans++;
        if(r == y)
        {
            cout << ans << '\n';
            continue;
        }
        bool f = 0;
        rep(i, r, y) if(e[y].X <= e[i].Y.X)
        {
            ans++, f = 1;
            break;
        }
        if(f) cout << ans << '\n';
        else cout << "impossible\n";
    }
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

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