Submission #967787

#	Time	Username	Problem	Language	Result	Execution time	Memory
967787		vladilius	Event Hopping (BOI22_events)	C++17	100 / 100	210 ms	29068 KiB

events

#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 (r[b] < r[a] || 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 (stderr)

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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30