oj.uz

Submission #967775

# Submission time Handle Problem Language Result Execution time Memory
967775 2024-04-22T19:44:01 Z vladilius Event Hopping (BOI22_events) C++17
0 / 100
 200 ms 31924 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = numeric_limits<int> :: max();
using pii = pair<int, int>;

struct ST{
    vector<pii> t;
    int n;
    ST(int ns){
        n = ns;
        t.assign(4 * n, {inf, 0});
    }
    
    pii merge(pii x, pii y){
        if (x.first < y.first){
            return x;
        }
        return y;
    }
    
    void upd(int v, int tl, int tr, int& pos, int& val, int& i){
        if (tl == tr){
            t[v] = merge(t[v], {val, i});
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (pos <= tm){
            upd(vv, tl, tm, pos, val, i);
        }
        else {
            upd(vv + 1, tm + 1, tr, pos, val, i);
        }
        t[v] = merge(t[vv], t[vv + 1]);
    }
    void upd(int p, int v, int i){
        upd(1, 1, n, p, v, i);
    }
    pii get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return {inf, 0};
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2, vv = 2 * v;
        return merge(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
    }
    pii get(int l, int r){
        return get(1, 1, n, l, r);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, q; cin>>n>>q;
    vector<int> l(n + 1), r(n + 1);
    vector<int> x;
    for (int i = 1; i <= n; i++){
        cin>>l[i]>>r[i];
        x.push_back(l[i]);
        x.push_back(r[i]);
    }
    sort(x.begin(), x.end());
    map<int, int> mp;
    int i = 0, cnt = 1;
    while (i < x.size()){
        int j = i;
        while (j < x.size() && x[i] == x[j]){
            j++;
        }
        mp[x[i]] = cnt++;
        i = j;
    }

    vector<int> st[2 * n + 1];
    for (int i = 1; i <= n; i++){
        st[mp[l[i]]].push_back(i);
    }
    
    // f[i] = min(s[k]: l[i] <= r[k] <= r[i])
    ST T(2 * n);
    for (int i = 1; i <= n; i++){
        T.upd(mp[r[i]], l[i], i);
    }
    vector<int> f(n + 1);
    for (int i = 1; i <= n; i++){
        int kl = mp[l[i]];
        f[i] = (T.get(kl, mp[r[i]])).second;
        if (f[i] == i){
            if (st[kl].size() > 1){
                if (st[kl][0] == i){
                    f[i] = st[kl][1];
                }
                else {
                    f[i] = st[kl][0];
                }
            }
        }
    }
    
    int lg = (int) ceil(log2(n));
    vector<vector<int>> sp(n + 1, vector<int>(lg + 1));
    
    for (int i = 1; i <= n; i++){
        sp[i][0] = f[i];
    }
    
    for (int k = 1; k <= lg; k++){
        for (int i = 1; i <= n; i++){
            sp[i][k] = sp[sp[i][k - 1]][k - 1];
        }
    }
    
    for (int i = 1; i <= n; i++){
        int j = lg;
        while (j >= 0 && sp[i][j] == sp[i][lg]){
            j--;
        }
        j += 2;
        while (j <= lg) sp[i][j++] = 0;
    }

    auto solve = [&](int a, int b){
        if (a == b) return 0;
        int out = 0;
        for (int i = lg; i >= 0; i--){
            if (a == b) return out;
            if (l[b] <= r[a] && r[a] <= r[b]){
                return (out + 1);
            }
            int rr = r[sp[b][i]];
            if (b == sp[b][i]) continue;
            if (rr >= l[a] && r[b] > rr){
                b = sp[b][i];
                out += (1 << i);
            }
        }
        if (a == b) return out;
        if (!(l[b] <= r[a] && r[a] <= r[b])){
            return -1;
        }
        return out + 1;
    };
    
    while (q--){
        int s, f; cin>>s>>f;
        int out = solve(s, f);
        if (out == -1){
            cout<<"impossible"<<"\n";
            continue;
        }
        cout<<out<<"\n";
    }
}

// WA

Compilation message

events.cpp: In function 'int main()':
events.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     while (i < x.size()){
      |            ~~^~~~~~~~~~
events.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while (j < x.size() && x[i] == x[j]){
      |                ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 200 ms 31824 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 31924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 200 ms 31824 KB Output isn't correct
3 Halted 0 ms 0 KB -