oj.uz

Submission #723330

# Submission time Handle Problem Language Result Execution time Memory
723330 2023-04-13T15:41:59 Z Mr_Husanboy Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 19940 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 Sparse{
    vector<vector<pair<int,int>>> t;
    int n, logn;
    pair<int,int> join(pair<int,int> a, pair<int,int> b){
        return min(a, b);
    }
    auto build(vector<int> &a){
        n = len(a);
        logn = 32 - __builtin_clz(n);
        t.assign(n, vector<pair<int,int>> (logn, pair{inf, 0}));
        for(int i = 0; i < n; i ++){
            t[i][0] = {a[i], i};
        }
        for(int j = 1; j < logn; j ++){
            for(int i = 0; i + (1 << j) <= n; i ++){
                t[i][j] = join(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int get(int l, int r){
        if(l > r) return inf;
        int len = r - l + 1;
        len = 31 - __builtin_clz(len);
        return join(t[l][len], t[r - (1 << len) + 1][len]).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));
    Sparse t;
    vector<int> 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 0 ms 212 KB Output is correct
2 Execution timed out 1575 ms 19940 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.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 1 ms 468 KB Output is correct
4 Correct 1 ms 340 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
15.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 1 ms 468 KB Output is correct
4 Correct 1 ms 340 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 0 ms 212 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 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 506 ms 1548 KB Output is correct
20 Correct 1480 ms 1776 KB Output is correct
21 Correct 297 ms 2784 KB Output is correct
22 Correct 24 ms 2976 KB Output is correct
23 Correct 23 ms 2752 KB Output is correct
24 Correct 22 ms 2752 KB Output is correct
25 Correct 48 ms 2428 KB Output is correct

Subtask #4
15.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 1 ms 468 KB Output is correct
4 Correct 1 ms 340 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 0 ms 212 KB Output is correct
11 Correct 1 ms 212 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 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 171 ms 19884 KB Output is correct
20 Correct 82 ms 19784 KB Output is correct
21 Correct 71 ms 19804 KB Output is correct
22 Correct 67 ms 19892 KB Output is correct
23 Correct 61 ms 19832 KB Output is correct
24 Correct 62 ms 19808 KB Output is correct
25 Correct 55 ms 19820 KB Output is correct

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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