oj.uz

Submission #579617

# Submission time Handle Problem Language Result Execution time Memory
579617 2022-06-19T13:46:21 Z Josia Event Hopping (BOI22_events) C++17
0 / 100
 310 ms 32212 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t



struct seg {
    vector<pair<int, int>> tree;

    seg(int n) {
        tree.assign(n*4, {1e18, -1});
    }

    void update(int v, int rl, int rr, int pos, pair<int, int> x) {
        if (rl == rr) {
            tree[v] = x;
            return;
        }
        int rm = (rl + rr) / 2;

        if (pos <= rm) update(v*2, rl, rm, pos, x);
        else update(v*2+1, rm+1, rr, pos, x);

        tree[v] = min(tree[v*2], tree[v*2+1]);
    }

    pair<int, int> query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) return {1e18, -1};
        if (rl == ql && rr == qr) return tree[v];

        int rm = (rl + rr) / 2;

        return min(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
    }
};




signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, q; cin >> n >> q;

    vector<tuple<int, int, int>> events(n);

    for (int i = 0; i<n; i++) {
        cin >> get<1>(events[i]) >> get<0>(events[i]);
        get<2>(events[i]) = i;    
    }

    sort(events.begin(), events.end());

    vector<pair<int, int>> segtreeRanges;

    for (auto i: events) {
        int l = upper_bound(events.begin(), events.end(), tuple<int, int, int>{get<1>(i)-1, 1e18, 1e18}) - events.begin();
        int r = upper_bound(events.begin(), events.end(), tuple<int, int, int>{get<0>(i), 1e18, 1e18}) - events.begin() - 1;
        segtreeRanges.push_back({l, r});
    }

    for (auto &i: events) swap(get<0>(i), get<1>(i));


    seg tree(n);

    for (int i = 0; i<n; i++) {
        tree.update(1, 0, n-1, i, {get<0>(events[i]), get<2>(events[i])});
    }


    vector<pair<int, int>> parents(n);

    for (int i = 0; i<n; i++) {
        parents[get<2>(events[i])] = tree.query(1, 0, n-1, segtreeRanges[i].first, segtreeRanges[i].second);
    }


    // for (auto i: parents) {
    //     cerr << i.first << " " << i.second << "\n";
    // }


    for (auto &i: events) swap(get<0>(i), get<2>(i));
    sort(events.begin(), events.end());
    for (auto &i: events) swap(get<0>(i), get<2>(i));



    vector<vector<int>> jump(n, vector<int>(20));


    for (int i = 0; i<20; i++) {
        for (int j = 0; j<n; j++) {
            if (i == 0) {jump[j][i] = parents[j].second; continue;}
            jump[j][i] = jump[jump[j][i-1]][i-1];
        }
    }



    for (int i = 0; i<q; i++) {
        int s, e; cin >> s >> e;
        s--;
        e--;

        if (s == e) {cout << 0 << "\n"; continue;}

        int cnt = 2;


        for (int i = 19; i>=0; i--) {
            if (get<0>(events[jump[e][i]]) > get<1>(events[s])) {
                e = jump[e][i];
                cnt += pow(2, i);
            }
        }

        e = parents[e].second;

        if (!(get<0>(events[e]) <= get<1>(events[s]) && get<1>(events[s]) <= get<1>(events[e]))) cout << "impossible\n";
        else cout << cnt << "\n";
    }



    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 159 ms 32136 KB Output is correct
3 Correct 180 ms 32196 KB Output is correct
4 Incorrect 310 ms 32180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 32120 KB Output is correct
2 Correct 220 ms 32180 KB Output is correct
3 Incorrect 290 ms 32212 KB Output isn't correct
4 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 Correct 159 ms 32136 KB Output is correct
3 Correct 180 ms 32196 KB Output is correct
4 Incorrect 310 ms 32180 KB Output isn't correct
5 Halted 0 ms 0 KB -