oj.uz

Submission #935660

# Submission time Handle Problem Language Result Execution time Memory
935660 2024-02-29T10:40:40 Z peterandvoi Event Hopping (BOI22_events) C++17
20 / 100
 100 ms 14360 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

#define MASK(x) (1LL << (x))

const int N = (int) 1e5 + 5;
const int LOG = 17;

int n, m, q;
pair<int, int> event[N];
int lg[N], pos[N];
int up[LOG][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> q;
    vector<int> R;
    for (int i = 1; i <= n; ++i) {
        cin >> event[i].first >> event[i].second;
        R.emplace_back(event[i].second);
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return event[i] < event[j];
    });
    for (int i = 0; i < n; ++i) {
        pos[ord[i]] = i + 1;
    }
    sort(event + 1, event + n + 1);
    auto cmb = [&](int x, int y) {
        if (x == -1) {
            return y;
        }
        if (y == -1) {
            return x;
        }
        return event[x].first < event[y].first ? x : y;
    };
    sort(R.begin(), R.end());
    R.erase(unique(R.begin(), R.end()), R.end());
    m = (int) R.size();
    vector<int> tree(4 << __lg(m), -1);
    auto upd = [&](int i, int x) {
        int id = 1, l = 1, r = m;
        while (l < r) {
            int mid = l + r >> 1;
            id <<= 1;
            if (i <= mid) {
                r = mid;
            } else {
                id |= 1;
                l = mid + 1;
            }
        }
        tree[id] = cmb(tree[id], x);
        while (id > 1) {
            id >>= 1;
            tree[id] = cmb(tree[id << 1], tree[id << 1 | 1]);
        }
    };
    auto get = [&](auto get, int u, int v, int id = 1, int l = 1, int r = m) {
        if (u <= l && r <= v) {
            return tree[id];
        }
        int mid = l + r >> 1;
        if (u <= mid && mid < v) {
            return cmb(get(get, u, v, id << 1, l, mid), get(get, u, v, id << 1 | 1, mid + 1, r));
        }
        if (u <= mid) {
            return get(get, u, v, id << 1, l, mid);
        }
        return get(get, u, v, id << 1 | 1, mid + 1, r);
    };
    for (int i = 1; i <= n; ++i) {
        int tr = upper_bound(R.begin(), R.end(), event[i].second) - R.begin();
        upd(tr, i);
    }
    for (int i = 1; i <= n; ++i) {
        int L = lower_bound(R.begin(), R.end(), event[i].first) - R.begin() + 1;
        int tr = upper_bound(R.begin(), R.end(), event[i].second) - R.begin();
        up[0][i] = get(get, L, tr);
    }
    for (int j = 1; j < LOG; ++j) {
        for (int i = 1; i <= n; ++i) {
            up[j][i] = up[j - 1][up[j - 1][i]];
        }
    }
    auto reach = [&](int u, int v) {
        if (v == -1) {
            return false;
        }
        return event[v].first <= event[u].second && event[u].second <= event[v].second;
    };
    auto qry = [&](int s, int t) {
        if (t == s) {
            cout << 0 << "\n";
            return;
        }
        if (t < s) {
            cout << "impossible\n";
            return;
        }
        if (event[t].first <= event[s].second) {
            cout << (reach(s, t) ? "1" : "impossible") << "\n";
            return;
        }
        int res = 0;
        for (int i = LOG - 1; i >= 0; --i) {
            int u = up[i][t];
            if (u != -1 && event[u].first > event[s].second) {
                t = u;
                res += MASK(i);
            }
        }
        t = up[0][t];
        if (reach(s, t)) {
            cout << res + 2 << "\n";
        } else {
            cout << "impossible\n";
        }
    };
    while (q--) {
        int s, t;
        cin >> s >> t;
        s = pos[s];
        t = pos[t];
        qry(s, t);
    }
}

Compilation message

events.cpp: In lambda function:
events.cpp:59:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |             int mid = l + r >> 1;
      |                       ~~^~~
events.cpp: In instantiation of 'main()::<lambda(auto:23, int, int, int, int, int)> [with auto:23 = main()::<lambda(auto:23, int, int, int, int, int)>]':
events.cpp:94:34:   required from here
events.cpp:78:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 99 ms 13780 KB Output is correct
3 Correct 96 ms 13932 KB Output is correct
4 Correct 95 ms 13776 KB Output is correct
5 Correct 93 ms 14036 KB Output is correct
6 Correct 93 ms 13776 KB Output is correct
7 Correct 93 ms 14032 KB Output is correct
8 Incorrect 88 ms 14284 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 13776 KB Output is correct
2 Correct 89 ms 13776 KB Output is correct
3 Correct 94 ms 13788 KB Output is correct
4 Correct 88 ms 14360 KB Output is correct
5 Correct 100 ms 14288 KB Output is correct
6 Correct 100 ms 14024 KB Output is correct
7 Correct 100 ms 13880 KB Output is correct
8 Correct 96 ms 14032 KB Output is correct
9 Correct 66 ms 11988 KB Output is correct
10 Correct 96 ms 13912 KB Output is correct
11 Correct 92 ms 13428 KB Output is correct
12 Correct 94 ms 13692 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 99 ms 13780 KB Output is correct
3 Correct 96 ms 13932 KB Output is correct
4 Correct 95 ms 13776 KB Output is correct
5 Correct 93 ms 14036 KB Output is correct
6 Correct 93 ms 13776 KB Output is correct
7 Correct 93 ms 14032 KB Output is correct
8 Incorrect 88 ms 14284 KB Output isn't correct
9 Halted 0 ms 0 KB -