oj.uz

Submission #694059

# Submission time Handle Problem Language Result Execution time Memory
694059 2023-02-03T16:53:54 Z finn__ Event Hopping (BOI22_events) C++17
0 / 100
 217 ms 22468 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int64_t, int64_t> Interval;

struct SegmentTree
{
    vector<pair<int64_t, unsigned>> t;
    size_t l;

    SegmentTree(size_t n)
    {
        l = 1U << (32U - __builtin_clz(n));
        t = vector<pair<int64_t, unsigned>>(2 * l, make_pair(INT64_MAX, UINT_MAX));
    }

    void update(size_t i, pair<int64_t, unsigned> const &x)
    {
        i += l;
        t[i] = min(t[i], x);
        i >>= 1;
        while (i)
        {
            t[i] = min(t[2 * i], t[2 * i + 1]);
            i >>= 1;
        }
    }

    pair<int64_t, unsigned> range_min(size_t i, size_t j)
    {
        i += l, j += l;
        pair<int64_t, unsigned> x = make_pair(INT64_MAX, UINT_MAX);

        while (i <= j)
        {
            if (i & 1)
                x = min(x, t[i++]);
            if (!(j & 1))
                x = min(x, t[j--]);
            i >>= 1;
            j >>= 1;
        }

        return x;
    }
};

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

    size_t n, q;
    cin >> n >> q;

    vector<Interval> intervals(n);
    vector<int64_t> coords;
    for (Interval &z : intervals)
    {
        cin >> z.first >> z.second;
        coords.push_back(z.first);
        coords.push_back(z.second);
    }
    sort(coords.begin(), coords.end());
    coords.resize(unique(coords.begin(), coords.end()) - coords.begin());

    SegmentTree tree(coords.size());
    vector<vector<unsigned>> pre(n);

    for (size_t i = 0; i < n; i++)
    {
        tree.update(
            lower_bound(coords.begin(), coords.end(), intervals[i].second) - coords.begin(),
            make_pair(intervals[i].first, i));
    }

    for (size_t i = 0; i < n; i++)
        pre[i].push_back(
            tree.range_min(
                    lower_bound(coords.begin(), coords.end(), intervals[i].first) - coords.begin(),
                    lower_bound(coords.begin(), coords.end(), intervals[i].second) - coords.begin())
                .second);

    for (size_t j = 1; j < 32U - __builtin_clz(n); j++)
    {
        for (size_t i = 0; i < n; i++)
        {
            if (j <= pre[i].size() && j <= pre[pre[i][j - 1]].size() &&
                pre[pre[i][j - 1]][j - 1] != pre[i][j - 1])
                pre[i].push_back(pre[pre[i][j - 1]][j - 1]);
        }
    }

    while (q--)
    {
        unsigned u, v;
        cin >> u >> v;
        u--, v--;

        if (u == v)
        {
            cout << "0\n";
            continue;
        }

        unsigned d = 0;
        for (unsigned i = pre[v].size() - 1; i < pre[v].size(); i--)
        {
            if (intervals[pre[v][i]].first > intervals[u].second)
                v = pre[v][i], d += 1U << i;
        }

        if (intervals[v].first > intervals[u].second)
            v = pre[v][0], d++;

        if (intervals[v].second >= intervals[u].second &&
            intervals[v].first <= intervals[u].second)
            cout << d + 1 << '\n';
        else
            cout << "impossible\n";
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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