oj.uz

Submission #967783

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

struct ST{
    vector<pii> t;
    int n;
    ST(int ns){
        n = ns;
        t.assign(4 * n, {inf, 0});
    }
    pii min(pii x, pii y){
        if (x.first < y.first){
            return x;
        }
        return y;
    }
    void upd(int v, int tl, int tr, int& p, pii& k){
        if (tl == tr){
            t[v] = min(t[v], k);
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, k);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, k);
        }
        t[v] = min(t[vv], t[vv + 1]);
    }
    void upd(int p, pii k){
        upd(1, 1, n, p, k);
    }
    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 min(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);
    for (int i = 1; i <= n; i++){
        cin>>l[i]>>r[i];
    }
    
    vector<int> all;
    for (int i = 1; i <= n; i++) all.push_back(l[i]);
    for (int i = 1; i <= n; i++) all.push_back(r[i]);
    sort(all.begin(), all.end());
    int i = 0, cnt = 0;
    map<int, int> mp;
    while (i < all.size()){
        int j = i;
        while (j < all.size() && all[i] == all[j]){
            j++;
        }
        mp[all[i]] = ++cnt;
        i = j;
    }
    for (int i = 1; i <= n; i++){
        l[i] = mp[l[i]];
        r[i] = mp[r[i]];
    }
    
    ST T(cnt);
    for (int i = 1; i <= n; i++){
        T.upd(r[i], {l[i], i});
    }
    
    const 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] = (T.get(l[i], r[i])).second;
    }
    
    for (int k = 1; k <= lg; k++){
        for (int i = 1; i <= n; i++){
            sp[i][k] = sp[sp[i][k - 1]][k - 1];
        }
    }
    
    function<void(int, int)> solve = [&](int a, int b){
        if (a == b){
            cout<<0<<"\n";
            return;
        }
        if (l[b] <= r[a] && r[a] <= r[b]){
            cout<<1<<"\n";
            return;
        }
        if (l[sp[b][lg]] > r[a]){
            cout<<"impossible"<<"\n";
            return;
        }
        
        int out = 1;
        for (int i = lg; i >= 0; i--){
            if (r[a] < l[sp[b][i]]){
                b = sp[b][i];
                out += (1 << i);
            }
        }
        out += (a != b);
        cout<<out<<"\n";
    };
    
    while (q--){
        int s, f; cin>>s>>f;
        solve(s, f);
    }
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 137 ms 20596 KB Output is correct
3 Correct 160 ms 20856 KB Output is correct
4 Correct 202 ms 20536 KB Output is correct
5 Correct 161 ms 21196 KB Output is correct
6 Correct 172 ms 22300 KB Output is correct
7 Correct 156 ms 22224 KB Output is correct
8 Correct 152 ms 28876 KB Output is correct
9 Correct 156 ms 29136 KB Output is correct
10 Incorrect 151 ms 20536 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 20568 KB Output is correct
2 Correct 158 ms 20540 KB Output is correct
3 Correct 177 ms 20596 KB Output is correct
4 Correct 154 ms 28884 KB Output is correct
5 Incorrect 156 ms 20684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 137 ms 20596 KB Output is correct
3 Correct 160 ms 20856 KB Output is correct
4 Correct 202 ms 20536 KB Output is correct
5 Correct 161 ms 21196 KB Output is correct
6 Correct 172 ms 22300 KB Output is correct
7 Correct 156 ms 22224 KB Output is correct
8 Correct 152 ms 28876 KB Output is correct
9 Correct 156 ms 29136 KB Output is correct
10 Incorrect 151 ms 20536 KB Output isn't correct
11 Halted 0 ms 0 KB -