Submission #788213

#	Time	Username	Problem	Language	Result	Execution time	Memory
788213		Ozy	Event Hopping (BOI22_events)	C++17	20 / 100	201 ms	36856 KiB

events

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 100000
#define lim (1ll<<60)
//para el vector de ordem
#define id second

lli n,q,cont,offset,s,e,a,res;
pll rangos[MAX+2];
vector<pll> orden;
pll stree[MAX*4];
set<pll> activos;
lli anc[MAX+2][22],uf[MAX+2];

lli sube(lli pos){
    if (uf[pos] == pos) return pos;
    uf[pos] = sube(uf[pos]);
    return uf[pos];
}

pll query(lli pos, lli ini, lli fin, lli l, lli r) {
    if (ini > r || fin < l) return {lim,lim};
    if (l <= ini && fin <= r) return stree[pos];

    lli mitad = (ini+fin)/2;
    pll a = query(pos*2,ini,mitad,l,r);
    pll b = query((pos*2)+1,mitad+1,fin,l,r);

    if (b.first < a.first) swap(a,b);
    return a;
}

void update(lli pos, lli ini, lli fin, lli des, pll newnode) {
    if (ini > des || fin < des) return;
    if (des <= ini && fin <= des) {
        stree[pos] = newnode;
        return;
    }

    lli mitad = (ini+fin)/2;
    lli izq = pos*2;
    lli der = (pos*2)+1;

    update(izq,ini,mitad,des,newnode);
    update(der,mitad+1,fin,des,newnode);

    if (stree[izq].first < stree[der].first) stree[pos] = stree[izq];
    else stree[pos] = stree[der];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    rep(i,1,n) {
        cin >> rangos[i].first >> rangos [i].second;
        orden.push_back({rangos[i].second, i});
    }
    sort(orden.begin(), orden.end());

    cont = 1;
    offset = 1;
    while (offset < n) offset *= 2;
    rep(i,1,offset*2-1) stree[i] = {lim,lim};

    for(auto act : orden) {

        auto it = activos.lower_bound({rangos[act.id].first,0});
        if(it != activos.end()) {
            a = (*it).second; //posicion en el stree;
            pll x = query(1,1,offset,a,cont-1);

            anc[act.id][0   ] = x.id;
            lli padre = x.id;
            rep(i,1,20) {
                anc[act.id][i] = anc[padre][i-1];
                padre = anc[act.id][i];
            }
        }

        activos.insert({act.first,cont});
        update(1,1,offset,cont,{rangos[act.id].first, act.id});
        cont++;
    }

    //uf para saber si es posible o no lo es
    rep(i,1,n) {
        if (anc[i][0] == 0) uf[i] = i;
        else uf[i] = anc[i][0];
    }

    //lee y responde las querys
    rep(Q,1,q) {

        cin >> s >> e;

        //debugsl(s);
        //debug(e);

        if (s == e) {
            cout << 0 << "\n";
            continue;
        }

        lli x = sube(s);
        lli y = sube(e);
        if (x != y || rangos[s].second > rangos[e].second) {
            cout << "impossible\n";
            continue;
        }

        res = 0;
        repa(i,20,0) {
            a = anc[e][i];
            if (a == 0) continue;
            if (rangos[a].first <= rangos[s].second) continue;
            else {
                e = a;
                res += (1<<i);
            }
        }
        res++;
        if(rangos[e].first > rangos[s].second) res++;

        cout << res << "\n";
    }

    return 0;
    //checar si el par lim, lim no tiene alguna repercucion
    //me falta checar si es posible
}

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