Submission #797134

#	Time	Username	Problem	Language	Result	Execution time	Memory
797134		TheSahib	Event Hopping (BOI22_events)	C++14	100 / 100	434 ms	29356 KiB

events

#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 2e5 + 5;
const pii dummy = {oo + 5, -1};

int n, q;
pii arr[MAX];

pii tree[MAX * 4];

void update(int node, int l, int r, int pos, pii val){
    if(l == r){
        tree[node] = min(tree[node], val);
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid){
        update(node * 2, l, mid, pos, val);
    }
    else{
        update(node * 2 + 1, mid + 1, r, pos, val);
    }
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}

pii ask(int node, int l, int r, int ql, int qr){
    if(ql > r || qr < l) return dummy;
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return min(ask(node * 2, l, mid, ql, qr), ask(node * 2 + 1, mid + 1, r, ql, qr));
}


bool comp(array<int, 3> a, array<int, 3> b){
    if(a[1] == b[1]) return a[0] < b[0];
    return a[1] < b[1];
}

int par[18][MAX];

int main()
{
    fill(tree, tree + MAX * 4, dummy);
    cin >> n >> q;
    map<int, int> mp;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].first >> arr[i].second;
        mp[arr[i].first];
        mp[arr[i].second];
    }
    int c = 0;
    for(auto& p:mp){
        p.second = ++c;
    }
    vector<array<int, 3>> v;
    for (int i = 0; i < n; i++)
    {
        arr[i].first = mp[arr[i].first];
        arr[i].second = mp[arr[i].second];
        v.push_back({arr[i].first, arr[i].second, i});
    }
    sort(v.begin(), v.end(), comp);
    for (int i = 0; i < n; i++)
    {
        update(1, 1, MAX, v[i][1], {v[i][0], v[i][2]});
        par[0][v[i][2]] = ask(1, 1, MAX, v[i][0], v[i][1]).second;
    }
    
    for (int j = 1; j < 18; j++)
    {
        for (int i = 0; i < n; i++)
        {
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    while(q--){
        int s, e; cin >> s >> e;
        s--;
        e--;
        if(s == e){
            cout << 0 << '\n';
            continue;
        }
        int dist = 0;
        int best = oo;
        int pos = false;
        for (int j = 17; j >= 0; j--)
        {
            int idx = par[j][e];
            if(arr[s].second < arr[idx].first){
                dist += (1 << j);
                e = idx;
            }
            else if(arr[s].second > arr[idx].second){
                continue;
            }
            else{
                pos = true;
                best = min(best, dist + (1 << j) + 1);
            }
        }
        if(arr[s].second >= arr[e].first && arr[s].second <= arr[e].second){
            pos = true;
            best = 1;
        }
        if(pos){
            cout << best << '\n';
        }
        else{
            cout << "impossible\n";
        }
    }
}

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