oj.uz

Submission #723329

# Submission time Handle Problem Language Result Execution time Memory
723329 2023-04-13T15:40:35 Z Mr_Husanboy Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 36532 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
    return a.size();
}
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;
#define ff first
#define ss second
 
struct SparseT{
    vector<vector<pair<ll,ll>>> t;
    int n, logn;
    pair<ll,ll> join(pair<ll,ll> a, pair<ll,ll> b){
        return min(a,b);
    }

    pair<ll,ll> neutral(){
        return {infl,infl};
    }

    SparseT (){}

    SparseT (int _n){
        init(_n);
    }

    SparseT (vector<ll> &a){
        build(a);
    }

    void init(int _n){
        n = _n;
        logn = 32 - __builtin_clz(n);
        t.assign(_n, vector<pair<ll,ll>>(logn, neutral()));
    }

    void build(vector<ll> &a){
        init((int)(a.size()));
        for(int i = 0; i < n; i ++){
            t[i][0] = {a[i], i};
        }

        for(int i = 1; i < logn; i ++){
            for(int j = 0; j + (1 << i) <= n; j ++){
                t[j][i] = join(t[j][i - 1], t[j + (1 << (i - 1))][i - 1]);
            }
        }
    }

    ll get(int l, int r){
        if(l > r) return neutral().ss;
        int k = 31 - __builtin_clz(r - l + 1);
        return join(t[l][k], t[r - (1 << k) + 1][k]).ss; 
    }
};
 
 
 
void solve(){
    int n, q; cin >> n >> q;
    vector<tuple<int,int,int>> e(n);
    vector<pair<int,int>> ev(n);
    for(int i = 0; i < n; i ++){
        auto &[r, l, id] = e[i];
        cin >> l >> r;
        ev[i] = {l, r};
        //l = -l;
        id = i; 
    }
    sort(all(e));
    SparseT t;
    vector<ll> lef(n);
    vector<int> pos(n);
    for(int i = 0; i < n; i ++){
        auto [r, l, id] = e[i];
        //l = -l;
        lef[i] = l;
        pos[id] = i;
        //cout << r << ' ' << l << endl;
    }
    t.build(lef);
    //for(auto u : lef) cout << u << ' '; cout << endl;
    vector<int> g(n);
    iota(all(g), 0);
    for(int i = 0; i < n; i ++){
        auto [r, l, id] = e[i];
        //l = -l;
        int ch = lower_bound(all(e), tuple{l, -1, -1}) - e.begin();
        //ch --;
        //cout << i << ' ' << ch << endl;
        int mn = t.get(ch, i);
        auto [rr, ll, idd] = e[mn];
        g[id] = idd;
    }
 //   for(int i = 0; i < n; i ++) cout << i << ' ' << g[i] << endl;
    while(q --){
        int a, b; cin >> a >> b; a --; b --;
        if(a == b){cout << "0\n"; continue;}
        bool ok = 0;
        int d = 0;
        while(g[b] != b){
            d ++;
            if(ev[a].ss > ev[b].ss){break;}
            if(ev[a].ss >= ev[b].ff){
                ok = 1; break;
            }
            b = g[b];
        }
        if(ev[a].ss >= ev[b].ff && ev[a].ss <= ev[b].ss && ok == 0){
            d ++; ok = 1; 
        }
        if(ok) cout << d << '\n'; else cout << "impossible\n";
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int testcases = 1;
    //cin >> testcases;
    while(testcases --){
        solve();
        if(testcases) cout << '\n';
        #ifdef LOCAL
        else cout << '\n';
        cout << "__________________" << endl;
        #endif
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Execution timed out 1579 ms 36532 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 540 ms 3272 KB Output is correct
20 Execution timed out 1538 ms 3236 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 2 ms 464 KB Output is correct
19 Correct 185 ms 36328 KB Output is correct
20 Correct 82 ms 35516 KB Output is correct
21 Correct 77 ms 36220 KB Output is correct
22 Correct 80 ms 36300 KB Output is correct
23 Correct 72 ms 36204 KB Output is correct
24 Correct 74 ms 36300 KB Output is correct
25 Correct 62 ms 35544 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1548 ms 36528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Execution timed out 1579 ms 36532 KB Time limit exceeded
3 Halted 0 ms 0 KB -