oj.uz

답안 #694105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
694105 2023-02-03T19:25:15 Z finn__ Event Hopping (BOI22_events) C++17
0 / 100
 176 ms 22388 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);
        while (i >>= 1)
            t[i] = min(t[2 * i], t[2 * 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());

    for (Interval &x : intervals)
    {
        x.first = lower_bound(coords.begin(), coords.end(), x.first) - coords.begin();
        x.second = lower_bound(coords.begin(), coords.end(), x.second) - coords.begin();
    }

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

    for (size_t i = 0; i < n; i++)
        tree.update(intervals[i].second, make_pair(intervals[i].first, i));

    for (size_t i = 0; i < n; i++)
    {
        unsigned const y =
            tree.range_min(intervals[i].first, intervals[i].second).second;
        if (y != i)
            pre[i].push_back(y);
    }

    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[i].push_back(pre[pre[i][j - 1]][j - 1]);
        }
    }

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

        if (intervals[u].second > intervals[v].second)
        {
            cout << "impossible\n";
            continue;
        }

        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]].second > intervals[u].second)
                v = pre[v][i], d += 1U << i;
        }

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 176 ms 22352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 22388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 176 ms 22352 KB Output isn't correct
3 Halted 0 ms 0 KB -