Submission #1191954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191954		wojaczek	Event Hopping (BOI22_events)	C++20	0 / 100	160 ms	47508 KiB

events

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= (int)b; ++i)
#define RFOR(i, a, b) for(int i = a; i >= (int)b; --i)
#define in insert
#define pb push_back
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define V vector
#define S set
#define eb emplace_back
#define P pair
#define MS multiset
#define BS bitset
using namespace std;

unordered_map<ll, bool> vis;
unordered_map<ll, ll> odp;
const int BASE = 1 << 20;
const int MAX = 1e6 + 7;
pair<ll, ll> tree[2 * BASE];
vector<pair<ll, ll>> input(1);
ll memo[MAX][23];

void update(ll v, pair<ll, ll> akt) {
    if(akt.f > tree[v].f) tree[v] = {akt.f, akt.s};
    while(v > 0) {
        v /= 2;
        if(tree[2 * v].f > tree[2 * v + 1].f) tree[v] = tree[2 * v];
        else tree[v] = tree[2 * v + 1];
    }
}

pair<ll, ll> query(ll v, ll a, ll b, ll c, ll d) {
    if(a > d || b < c) return {0, 0};
    if(a >= c && b <= d) return tree[v];
    pair<ll, ll> w1 = query(2 * v, a, (a + b) / 2, c, d);
    pair<ll, ll> w2 = query(2 * v + 1, (a + b) / 2 + 1, b, c, d);
    if(w1.f > w2.f) return w1;
    else return w2;
}

ll calc(ll a, ll b) {
    if(input[b].f < input[a].f) return INT_MAX;
    if(input[a].f == input[b].f && input[a].s == input[b].s) return 0;
    ll res = 0;
    RFOR(j, 21, 0) {
        if(memo[a][j] && input[memo[a][j]].s < input[b].f) {
            a = memo[a][j];
            res += (1 << j);
        }
    }
    ll anc = memo[a][0];
    if(anc == 0) return INT_MAX; 
    if(input[anc].f == input[b].f && input[anc].s == input[b].s) return res + 1;
    else return res + 2;
}

void solve() {
    ll n, q; cin >> n >> q;
    //konwersja wspolrzednych
    vector<ll> nums;
    FOR(i, 1, n) {
        ll a, b; cin >> a >> b;
        input.pb({a, b});
        if(!vis[a]) {vis[a] = true; nums.pb(a);}
        if(!vis[b]) {vis[b] = true; nums.pb(b);}
    }
    sort(nums.begin(), nums.end());
    FOR(i, 0, nums.size() - 1) odp[nums[i]] = i + 1;
    FOR(i, 1, input.size() - 1) {
        pair<ll, ll> akt = input[i];
        akt.f = odp[akt.f], akt.s = odp[akt.s];
        input[i] = akt;
    }
    //setupowanie drzewa przedzialowego
    FOR(i, 1, input.size() - 1) {
        pair<ll, ll> akt = input[i];
        update(akt.f + BASE - 1, {akt.s, i});
    }
    //tworzenie "drzewa" przedzialow
    FOR(i, 1, input.size() - 1) {
        pair<ll, ll> akt = input[i];
        ll p = akt.f, k = akt.s;
        pair<ll, ll> pr = query(1, 1, BASE - 1, p, k);
        ll idx = pr.s; 
        if(idx != i) memo[i][0] = idx;
    }
    //tablica "memo"
    FOR(j, 1, 21) FOR(i, 1, n) memo[i][j] = memo[memo[i][j - 1]][j - 1];
    FOR(i, 1, q) {
        ll a, b; cin >> a >> b;
        ll res = calc(a, b);
        if(res == INT_MAX) cout << "impossible" << '\n';
        else cout << res << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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