Submission #717643

#	Time	Username	Problem	Language	Result	Execution time	Memory
717643		adrilen	Event Hopping (BOI22_events)	C++17	100 / 100	299 ms	18460 KiB

events

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 1e5, bits = 17, siz = (1 << bits);

pii segtree[siz * 2];

void update(int val, int p,  int pos)
{
    while (pos != 0)
    {
        if (val < segtree[pos].first) segtree[pos] = pii(val, p);
        pos /= 2;
    }
}

pii query(int pos, int l, int r, int gl, int gr)
{
    if (l > gr || gl > r) return pii(1e9, 0);
    if (gl <= l && r <= gr) return segtree[pos];

    int mid = (l + r) >> 1;
    return min(query(pos * 2, l, mid, gl, gr), query(pos * 2 + 1, mid + 1, r, gl, gr));
}

struct ev {
    int s, e;
} ;


int dist[bits][maxn] = { 0 };
vector <ev> events;

int find_dist(int goal, int p, int last)
{
    if (p == last) return -2e9;
    for (int i = bits - 1; i >= 0; i--)
    {
        if (events[dist[i][p]].s <= events[goal].e) continue;
        return find_dist(goal, dist[i][p], p) + (1 << i);
    }
    return 0;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, q;
    cin >> n >> q;
    
    events.assign(n, ev{0, 0});

    int next_num = 0;
    map <int, int> num_map;
    for (ev &e : events) {
        cin >> e.s >> e.e;
        num_map[e.e] = 0;
    }

    for (auto &p : num_map) p.second = next_num++;

    for (ev &e : events) {
        e.e = num_map[e.e];
        e.s = (*num_map.lower_bound(e.s)).second;

        // cout << e.s << " " << e.e << "\n";
    }

    for (int i = 1; i <= next_num + siz; i++) segtree[i].first = 1e9;

    // for (int i = 1; i < siz + n; i++) 
    // {
    //     if (__builtin_popcount(i) == 1) cout << "\n";
    //     cout << segtree[i].first << " ";
    // }

    for (int i = 0; i < n; i++)
    {
        update(events[i].s, i, events[i].e + siz);
        //segtree[events[i].e] = min(segtree[events[i].e], pii(events[i].s, i));
    }

    // for (int i = 1; i < siz + n; i++) 
    // {
    //     if (__builtin_popcount(i) == 1) cout << "\n";
    //     cout << segtree[i].first << " " << segtree[i].second << "\t";
    // }

    // cout << "\n";

    for (int i = 0; i < n; i++)
    {
        dist[0][i] = query(1, 0, siz - 1, events[i].s, events[i].e).second;
        // cout << dist[0][i] << "\n";
    }

    // cerr << "output\n";

    for (int y = 1; y < bits; y++) 
    {
        for (int i = 0; i < n; i++) {
            dist[y][i] = dist[y - 1][dist[y - 1][i]];
        }
    }

    int a, b, val;
    while (q--)
    {
        cin >> a >> b;
        a--, b--;

        if (a == b)
        {
            cout << "0\n";
            continue;
        }

        if (events[a].e > events[b].e) {
            cout << "impossible\n";
            continue;
        }
        
        if (events[a].e >= events[b].s) {
            cerr << "fast ";
            cout << "1\n";
            continue;
        }

        val = find_dist(a, b, -1);
        if (val < 0) cout << "impossible\n";
        else {
            cout << val + 2 << "\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