oj.uz

Submission #721802

# Submission time Handle Problem Language Result Execution time Memory
721802 2023-04-11T07:27:10 Z sunnat Event Hopping (BOI22_events) C++14
20 / 100
 441 ms 17780 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
vector<int> l, r, si, ids;
vector<vector<int> > parent;
int n, q;
const int psize = 17;
struct Segment_Tree{
    vector<int> t;

    void build(int v, int l, int r){
        if(l == r){
            t[v] = si[l-1];
            return;
        }
        int m = (l + r) >> 1;
        build(v<<1, l, m);
        build(v<<1|1, m+1, r);
        t[v] = ::l[t[v<<1]] <= ::l[t[v<<1|1]] ? t[v<<1] : t[v<<1|1];
    }

    int get(int v, int l, int r, int L, int R){
        if(L == l && R == r) return t[v];
        int m = (l + r) >> 1;
        if(m < L) return get(v<<1|1, m+1, r, L, R);
        if(m >= R) return get(v<<1, l, m, L, R);
        int i = get(v<<1|1, m+1, r, m+1, R);
        int j = get(v<<1, l, m, L, m);
        return ::l[j] <= ::l[i] ? j : i;
    }

    int get(int l, int r){
        return ids[get(1, 1, n, l+1, r+1)];
    }

    void build(){
        t.resize(n<<2);
        build(1, 1, n);
    }
};

int main(){
    cin >> n >> q;
    l.resize(n);
    r.resize(n);
    si.resize(n);
    ids.resize(n);
    parent.resize(n, vector<int>(psize, -1));

    for(int i = 0; i < n; i ++){
        cin >> l[i] >> r[i];
        // r[i] --;
        si[i] = i;
    }
    sort(si.begin(), si.end(), [&](int r, int l){
        return ::r[r] != ::r[l] ? ::r[r] < ::r[l] : ::l[r] < ::l[r];
    });
    
    for(int i = 0; i < n; i ++) ids[si[i]] = i;
    
    Segment_Tree st;
    st.build();
    for(int i = 0, l, r, m; i < n; i ++){
        l = 0;
        r = i;
        while(l < r){
            m = (l + r) >> 1;
            if(::r[si[m]] >= ::l[si[i]]) r = m;
            else l = m + 1;
        }
        l = st.get(l, i);
        if(::l[si[l]] != ::l[si[i]]){
            parent[i][0] = l;
            for(int j = 1; j < psize; j ++){
                if(parent[parent[i][j-1]][j-1] != -1)
                    parent[i][j] = parent[parent[i][j-1]][j-1];
                else break;
            }
        }
    }

    for(int i = 0, u, v, cnt = 0; i < q; i ++){
        cin >> u >> v;
        u --;
        v --;
        if(u == v){
            cout << "0\n";
            continue;
        }
        if(l[v] <= r[u] && r[u] <= r[v]){
            cout << 1 << '\n';
            continue;
        }
        u = ids[u];
        v = ids[v];
        if(u > v){
            cout << "impossible\n";
            continue;
        }
        cnt = 0;
        for(int i = psize - 1; i >= 0; i --){
            if(parent[v][i] != -1 && l[si[parent[v][i]]] > r[si[u]]){
                cnt += 1<<i;
                v = parent[v][i];
            }
        }
        if(parent[v][0] == -1) cout << "impossible\n";
        else cout << cnt + 2 << "\n";
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 319 ms 14648 KB Output is correct
3 Correct 347 ms 14568 KB Output is correct
4 Correct 392 ms 14496 KB Output is correct
5 Correct 441 ms 14628 KB Output is correct
6 Correct 341 ms 17328 KB Output is correct
7 Correct 321 ms 17356 KB Output is correct
8 Incorrect 273 ms 17780 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 2 ms 340 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 326 ms 14860 KB Output is correct
2 Correct 322 ms 14796 KB Output is correct
3 Correct 336 ms 14812 KB Output is correct
4 Correct 269 ms 15252 KB Output is correct
5 Correct 339 ms 14868 KB Output is correct
6 Correct 387 ms 14632 KB Output is correct
7 Correct 343 ms 17456 KB Output is correct
8 Correct 309 ms 17488 KB Output is correct
9 Correct 102 ms 15436 KB Output is correct
10 Correct 335 ms 17004 KB Output is correct
11 Correct 292 ms 16884 KB Output is correct
12 Correct 310 ms 17140 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 319 ms 14648 KB Output is correct
3 Correct 347 ms 14568 KB Output is correct
4 Correct 392 ms 14496 KB Output is correct
5 Correct 441 ms 14628 KB Output is correct
6 Correct 341 ms 17328 KB Output is correct
7 Correct 321 ms 17356 KB Output is correct
8 Incorrect 273 ms 17780 KB Output isn't correct
9 Halted 0 ms 0 KB -