oj.uz

Submission #1098033

# Submission time Handle Problem Language Result Execution time Memory
1098033 2024-10-08T20:54:34 Z rifat414141 Event Hopping (BOI22_events) C++17
20 / 100
 85 ms 30100 KB 
#include <bits/stdc++.h>
#define int long long int
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e18;
const int LOGN = 20;
int arr[N];
pair<int, int> segment_tree[4 * N];
int up[N][LOGN];
int par[N];
void build(int id, int l, int r)
{
    if (l == r)
    {
        segment_tree[id] = {arr[l - 1], l - 1};
        return;
    }
    int mid = (l + r) / 2;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);
    segment_tree[id] = min(segment_tree[2 * id], segment_tree[2 * id + 1]);
    return;
}
pair<int, int> range(int id, int l, int r, int L, int R)
{
    if (R < l || L > r)
    {
        return {INF, INF};
    }
    if (L <= l && r <= R)
    {
        return segment_tree[id];
    }
    int mid = (l + r) / 2;
    pair<int, int> x = range(2 * id, l, mid, L, R);
    pair<int, int> y = range(2 * id + 1, mid + 1, r, L, R);
    return min(x, y);
}
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<pair<int, int>> v1;
    vector<pair<int, pair<int, int>>> v2;
    for (int i = 0; i < n; ++i)
    {
        int l, r;
        cin >> l >> r;
        v1.push_back({l, r});
        v2.push_back({r, {l, i}});
    }
    int brr[n];
    sort(v2.begin(), v2.end());
    for (int i = 0; i < n; ++i)
    {
        arr[i] = v2[i].second.first;
        brr[v2[i].second.second] = i;
    }
    build(1, 1, n);
    for (int i = 0; i < n; ++i)
    {
        pair<int, pair<int, int>> p = {v2[i].second.first, {-1, -1}};
        int it = lower_bound(v2.begin(), v2.end(), p) - v2.begin();
        // cout << v2[i].first << ' ' << it << endl;
        if (it == i)
        {
            up[i][0] = par[i] = i;
        }
        else
        {
            auto idx = range(1, 1, n, it + 1, i + 1);
            up[i][0] = par[i] = idx.second;
        }
    }
    for (int i = 1; i < LOGN; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    while (q--)
    {
        int s, e;
        cin >> s >> e;
        if (s == e)
        {
            cout << 0 << endl;
            continue;
        }
        s--, e--;
        s = brr[s], e = brr[e];
        int sl = v2[s].second.first, sr = v2[s].first;
        int el = v2[e].second.first, er = v2[e].first;
        if (s > e)
        {
            if (sl >= el && sr <= er)
            {
                cout << 1 << endl;
                continue;
            }
            else
            {
                cout << "impossible" << endl;
                continue;
            }
        }
        int curr = e;
        int ans = 0;
        for (int i = LOGN - 1; i >= 0; --i)
        {
            if (v2[up[curr][i]].first > sr)
            {
                ans += (1 << i);
                curr = up[curr][i];
            }
        }
        if (v2[up[curr][0]].first > sr)
        {
            ans++;
            curr = up[curr][0];
        }
        ans++;
        curr = up[curr][0];
        if (v2[curr].first > sr)
        {
            cout << "impossible" << endl;
            continue;
        }
        else
        {
            cout << ans << endl;
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("prime_subtractorization_input.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int t = 1;
    // cin >> t;
    for (int tt = 1; tt <= t; ++tt)
    {
        // cout << "Case #" << tt << ": ";
        solve();
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 67 ms 29248 KB Output is correct
3 Correct 71 ms 29512 KB Output is correct
4 Correct 73 ms 29252 KB Output is correct
5 Correct 69 ms 29252 KB Output is correct
6 Correct 69 ms 29252 KB Output is correct
7 Correct 68 ms 29248 KB Output is correct
8 Incorrect 56 ms 29764 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 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Incorrect 1 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 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Incorrect 1 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 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Incorrect 1 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 67 ms 29768 KB Output is correct
2 Correct 69 ms 29764 KB Output is correct
3 Correct 74 ms 29248 KB Output is correct
4 Correct 56 ms 29764 KB Output is correct
5 Correct 81 ms 29596 KB Output is correct
6 Correct 84 ms 29508 KB Output is correct
7 Correct 85 ms 29360 KB Output is correct
8 Correct 73 ms 30100 KB Output is correct
9 Correct 46 ms 28756 KB Output is correct
10 Correct 75 ms 29316 KB Output is correct
11 Correct 70 ms 28996 KB Output is correct
12 Correct 77 ms 29512 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 67 ms 29248 KB Output is correct
3 Correct 71 ms 29512 KB Output is correct
4 Correct 73 ms 29252 KB Output is correct
5 Correct 69 ms 29252 KB Output is correct
6 Correct 69 ms 29252 KB Output is correct
7 Correct 68 ms 29248 KB Output is correct
8 Incorrect 56 ms 29764 KB Output isn't correct
9 Halted 0 ms 0 KB -