oj.uz

Submission #788213

# Submission time Handle Problem Language Result Execution time Memory
788213 2023-07-20T01:32:52 Z Ozy Event Hopping (BOI22_events) C++17
20 / 100
 201 ms 36856 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);
            }
        }
        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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 134 ms 36744 KB Output is correct
3 Correct 174 ms 36832 KB Output is correct
4 Correct 183 ms 36744 KB Output is correct
5 Incorrect 179 ms 36752 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 344 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Incorrect 1 ms 596 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 344 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Incorrect 1 ms 596 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 344 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Incorrect 1 ms 596 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 144 ms 36856 KB Output is correct
2 Correct 158 ms 36792 KB Output is correct
3 Correct 201 ms 36828 KB Output is correct
4 Correct 81 ms 18752 KB Output is correct
5 Correct 144 ms 36460 KB Output is correct
6 Correct 176 ms 35652 KB Output is correct
7 Correct 159 ms 35604 KB Output is correct
8 Correct 153 ms 35776 KB Output is correct
9 Correct 111 ms 33728 KB Output is correct
10 Correct 159 ms 35264 KB Output is correct
11 Correct 132 ms 35008 KB Output is correct
12 Correct 152 ms 35204 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 134 ms 36744 KB Output is correct
3 Correct 174 ms 36832 KB Output is correct
4 Correct 183 ms 36744 KB Output is correct
5 Incorrect 179 ms 36752 KB Output isn't correct
6 Halted 0 ms 0 KB -