Submission #1246239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246239		slivajan	Event Hopping (BOI22_events)	C++20	100 / 100	133 ms	25672 KiB

events

#include <bits/stdc++.h>
using namespace std;

using un = long long;
using vuc = vector<un>;
using vol = vector<bool>;
using puc = pair<un, un>;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

constexpr un INF = INT64_MAX;

struct iv_tree {

    vec<puc> tree;
    un N;


    iv_tree(const vec<puc>& initial){
        N = initial.size();
        while(N&(N-1))N++;

        tree = vec<puc>(2*N, {INF, -1});

        REP(i, 0, initial.size()) tree[N+i] = initial[i];

        for (un i = N-1; i > 0; i--) tree[i] = min(tree[2*i], tree[2*i + 1]);
    }


    un dostat(un L, un R){
        return dostatRec(L, R, 1, 0, N-1).second;
    }

    puc dostatRec(un L, un R, un v, un vL, un vR){
        if ((R < vL) or (vR < L)) return {INF, -1};
        if ((L <= vL) and (vR <= R)) return tree[v];

        un vM = (vL+vR)/2;
        return min(dostatRec(L, R, 2*v, vL, vM), dostatRec(L, R, 2*v+1, vM+1, vR));
    }

};


int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    un N, Q; cin >> N >> Q;

    un log_N = 0;
    un _N = N;
    while(_N > 0) {
        _N/=2; log_N++;
    }

    vec<tuple<un, un, un>> toSort(N);
    REP(i, 0, N){
        un s, e; cin >> s >> e;
        toSort[i] = {e, s, i};
    }

    sort(ALL(toSort));

    vuc starts(N), ends(N), preklad(N);
    REP(i, 0, N) {
        un k;
        tie(ends[i], starts[i], k) = toSort[i];
        preklad[k] = i;
    }

    vec<puc> toIV(N);
    REP(i, 0, N) toIV[i] = {starts[i], i};

    iv_tree IV(toIV);

    vuc edges(N);

    REP(i, 0, N){
        un S = starts[i];
        un E = ends[i];

        un L = lower_bound(ALL(ends), S) - ends.begin();
        un R = upper_bound(ALL(ends), E) - ends.begin();
        R--;

        edges[i] = IV.dostat(L, R);
        if (starts[i] == starts[edges[i]]) edges[i] = -1;
    }


    vec<vuc> skocky(log_N, vuc(N));

    skocky[0] = move(edges);

    REP(e, 1, log_N){
        REP(i, 0, N){
            if (skocky[e-1][i] == -1) skocky[e][i] = -1;
            else skocky[e][i] = skocky[e-1][skocky[e-1][i]];
        }
    }


    REP(q, 0, Q){
        un S, E; cin >> S >> E;
        S--; E--;
        S = preklad[S];
        E = preklad[E];

        if (S == E) {
            cout << "0\n";
            continue;
        }

        un now = E;
        un konec = ends[S];

        if ((starts[now] <= konec) and (konec <= ends[now])){
            cout << "1\n";
            continue;
        }

        un ret = 0;

        un k = log_N-1;
        while(k >= 0){
            while ((skocky[k][now] != -1) and (konec < starts[skocky[k][now]]))
            {
                now = skocky[k][now];
                ret += 1<<k;
            }
            k--;
        }

        if (skocky[0][now] != -1){
            now = skocky[0][now];
            ret += 1;
        }

        if ((starts[now] <= konec) and (konec < ends[now])){
            cout << ret+1 << "\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