oj.uz

Submission #1098032

# Submission time Handle Problem Language Result Execution time Memory
1098032 2024-10-08T20:51:44 Z rifat414141 Event Hopping (BOI22_events) C++17
20 / 100
 84 ms 33088 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];
            }
        }
        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 32360 KB Output is correct
3 Correct 69 ms 32324 KB Output is correct
4 Correct 76 ms 32616 KB Output is correct
5 Correct 75 ms 32300 KB Output is correct
6 Correct 70 ms 32464 KB Output is correct
7 Correct 71 ms 32580 KB Output is correct
8 Incorrect 56 ms 33088 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 6488 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 6488 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 6488 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 6488 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 6488 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 6488 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 70 ms 32456 KB Output is correct
2 Correct 72 ms 32284 KB Output is correct
3 Correct 78 ms 32332 KB Output is correct
4 Correct 57 ms 32868 KB Output is correct
5 Correct 79 ms 33088 KB Output is correct
6 Correct 82 ms 32628 KB Output is correct
7 Correct 84 ms 32572 KB Output is correct
8 Correct 75 ms 32576 KB Output is correct
9 Correct 46 ms 30708 KB Output is correct
10 Correct 74 ms 32064 KB Output is correct
11 Correct 69 ms 32320 KB Output is correct
12 Correct 79 ms 32584 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 32360 KB Output is correct
3 Correct 69 ms 32324 KB Output is correct
4 Correct 76 ms 32616 KB Output is correct
5 Correct 75 ms 32300 KB Output is correct
6 Correct 70 ms 32464 KB Output is correct
7 Correct 71 ms 32580 KB Output is correct
8 Incorrect 56 ms 33088 KB Output isn't correct
9 Halted 0 ms 0 KB -