Submission #584524

#	Time	Username	Problem	Language	Result	Execution time	Memory
584524		AriaH	Event Hopping (BOI22_events)	C++17	100 / 100	134 ms	12300 KiB

events

/* Ignore Others Only Focus On Yourself! */
/* Im the Best! */

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

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

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

int n, q, S[N], E[N], id[N], nxt[LOG][N];

bool cmp(int i, int j)
{
    return (E[i] != E[j]? E[i] < E[j] : S[i] < S[j]);
}

int main()
{
	fast_io;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++)
    {
        cin >> S[i] >> E[i];
        id[i] = i;
    }
    sort(id + 1, id + n + 1, cmp);
    vector < pii > vec;
    for(int i2 = 1; i2 <= n; i2 ++)
    {
        int i = id[i2];
        ///printf("i = %d\n", i);
        while(SZ(vec) && S[i] <= S[vec.back().S])
        {
            vec.pop_back();
        }
        vec.push_back(Mp(E[i], i));
        nxt[0][i] = vec[lower_bound(all(vec), Mp(S[i], -1)) - vec.begin()].S;
        ///printf("nxt0 = %d\n", nxt[0][i]);
    }
    for(int T = 1; T < LOG; T ++)
    {
        for(int i = 1; i <= n; i ++)
        {
            nxt[T][i] = nxt[T - 1][nxt[T - 1][i]];
        }
    }
    while(q --)
    {
        int a, b;
        cin >> a >> b;
        if(E[a] > E[b])
        {
            cout << "impossible\n";
            continue;
        }
        if(a == b)
        {
            cout << 0 << endl;
            continue;
        }
        if(S[b] <= E[a])
        {
            cout << 1 << endl;
            continue;
        }
        int tot = 0;
        for(int T = LOG - 1; ~T; T --)
        {
            if(E[a] < S[nxt[T][b]])
            {
                tot ^= 1 << T;
                b = nxt[T][b];
            }
        }
        if(S[nxt[0][b]] > E[a])
        {
            cout << "impossible\n";
            continue;
        }
        cout << tot + 2 << endl;
    }
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

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