oj.uz

Submission #788215

# Submission time Handle Problem Language Result Execution time Memory
788215 2023-07-20T01:37:04 Z Ozy Event Hopping (BOI22_events) C++17
20 / 100
 235 ms 33956 KB 
#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);
            }
        }

        if(rangos[e].first > rangos[s].second) {
            res++;
            e = anc[e][0];
        }
        if (s != e) 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 141 ms 33876 KB Output is correct
3 Correct 140 ms 33948 KB Output is correct
4 Correct 217 ms 33900 KB Output is correct
5 Incorrect 150 ms 33876 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 616 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 616 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 616 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 33916 KB Output is correct
2 Correct 160 ms 33896 KB Output is correct
3 Correct 235 ms 33956 KB Output is correct
4 Correct 82 ms 16104 KB Output is correct
5 Correct 147 ms 33588 KB Output is correct
6 Correct 186 ms 32852 KB Output is correct
7 Correct 166 ms 32716 KB Output is correct
8 Correct 127 ms 32952 KB Output is correct
9 Correct 86 ms 32076 KB Output is correct
10 Correct 164 ms 32368 KB Output is correct
11 Correct 138 ms 32192 KB Output is correct
12 Correct 160 ms 32432 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 141 ms 33876 KB Output is correct
3 Correct 140 ms 33948 KB Output is correct
4 Correct 217 ms 33900 KB Output is correct
5 Incorrect 150 ms 33876 KB Output isn't correct
6 Halted 0 ms 0 KB -