oj.uz

Submission #946540

# Submission time Handle Problem Language Result Execution time Memory
946540 2024-03-14T18:17:05 Z vladilius Railway Trip 2 (JOI22_ho_t4) C++17
0 / 100
 104 ms 29644 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, k; cin>>n>>k>>m;
    vector<pii> s1, s2;
    while (m--){
        int a, b; cin>>a>>b;
        if (a > b) s1.push_back({b, a});
        else s2.push_back({a, b});
    }
    int lg = ceil(log2(n));
    pii sp[n + 1][lg + 1];
    for (int i = 1; i <= n; i++){
        sp[i][0] = {i, i};
    }
    
    auto mr = [&](pii x, pii y) -> pii{
        return {min(x.first, y.first), max(x.second, y.second)};
    };
    
    vector<int> in[n + 1], out[n + 1];
    for (auto [x, y]: s1){
        int l = max(x + 1, y - k + 1);
        in[l].push_back(x);
        out[y].push_back(x);
    }
    multiset<int> st;
    for (int i = 1; i <= n; i++){
        for (int j: in[i]){
            st.insert(j);
        }
        if (!st.empty()){
            sp[i][0].first = *st.begin();
        }
        for (int j: out[i]){
            st.erase(st.find(j));
        }
    }
    
    for (int i = 1; i <= n; i++){
        in[i].clear();
        out[i].clear();
    }
    for (auto [x, y]: s2){
        int l = max(x + 1, y - k + 1);
        in[x].push_back(y);
        out[l].push_back(y);
    }
    for (int i = 1; i <= n; i++){
        for (int j: in[i]){
            st.insert(j);
        }
        if (!st.empty()){
            sp[i][0].second = *prev(st.end());
        }
        for (int j: out[i]){
            st.erase(st.find(j));
        }
    }
        
    for (int j = 1; j <= lg; j++){
        for (int i = 1; i + (1 << j) <= n + 1; i++){
            pii T = sp[i][j - 1];
            sp[i][j] = mr(mr(T, sp[T.first][j - 1]), sp[T.second][j - 1]);
        }
    }
    
    auto can = [&](pii x, int p) -> bool{
        return (x.first <= p && p <= x.second);
    };
    
    int q; cin>>q;
    while (q--){
        int s, t; cin>>s>>t;
        int p = 0;
        while (sp[s][p].first) p++;
        if (!can(sp[s][p - 1], t)){
            cout<<-1<<"\n";
            continue;
        }
        pii cur = {s, s};
        int out = 1;
        for (int i = lg; i >= 0; i--){
            pii m = mr(cur, sp[cur.second][i]);
            if (!can(m, t)){
                out++;
                cur = m;
            }
        }
        cout<<out<<"\n";
    }
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 29644 KB Output is correct
2 Incorrect 89 ms 27940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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