Submission #599216

#	Time	Username	Problem	Language	Result	Execution time	Memory
599216		Vanilla	Event Hopping (BOI22_events)	C++17	100 / 100	546 ms	235792 KiB

events

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 2e5 + 2;
const int lg = 20;

struct node {
    int l,r;
    pair <int, int> v;

    node* left;
    node* right;

    node(int _l, int _r, pair <int, int> _v): l(_l), r(_r), v(_v) {};
    
    inline void extend() {
        if (left != NULL) return;
        int mid = (l + r) / 2;
        left = new node(l, mid, {1e9, -1});
        right = new node(mid + 1, r, {1e9, -1});
    }

    inline pair <int, int> query (int il, int ir) {
        if (il <= l && r <= ir) return v;
        if (l > ir || r < il) return {1e9, -1};
        extend();
        return min(left->query(il, ir), right->query(il, ir));
    }

    inline void update (int x, pair <int, int> nval) {
        if (l == r && l == x) return void(v = min(nval, v));
        if (l > x || r < x) return;
        extend();
        left->update(x, nval);
        right->update(x, nval);
        v = min(left->v, right->v);
    }
};
 
struct nd {
    int x;
    int y;
} a [maxn];

int bin[maxn][lg];
int n,q;
int ps[maxn];
node *sgt = new node(1, 1e9, {1e15, -1});


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        cin >> a[i].x >> a[i].y;
    }
    for (int i = 0; i < n; i++){
        sgt->update(a[i].y, {a[i].x, i});
    }
    for (int i = 0; i < n; i++){
        bin[i][0] = sgt->query(a[i].x, a[i].y).second;
    }
    for (int k = 1; k < lg; k++){
        for (int i = 0; i < n; i++){
            bin[i][k] = bin[bin[i][k-1]][k-1];
        }
    }
    while (q--){
        int x,y, rs = 2;
        cin >> x >> y;
        x--, y--;
        if (x == y) cout << "0\n";
        else if (a[x].y > a[y].y) cout << "impossible\n";
        else if (a[x].y >= a[y].x) cout << "1\n";
        else {
            for (int i = lg - 1; i >= 0; i--){
                if (a[bin[y][i]].x > a[x].y) y = bin[y][i], rs+=(1 << i);
            }
            if (a[bin[y][0]].x > a[x].y) cout << "impossible\n";
            else cout << rs << "\n";
        }
    }
    return 0;
}

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