Submission #711974

#	Time	Username	Problem	Language	Result	Execution time	Memory
711974		Johann	Event Hopping (BOI22_events)	C++14	100 / 100	245 ms	19568 KiB

events

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef tuple<int, int, int> tiii;
typedef vector<tiii> vtiii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

struct event
{
    int s, e, idx;
};

struct segtree
{
    vpii arr;
    int size;
    void init(vector<event> &E)
    {
        size = 1;
        while (size < sz(E))
            size *= 2;
        arr.assign(2 * size, {INT_MAX, -1});
        for (int i = 0; i < sz(E); ++i)
            arr[i + size] = {E[i].s, E[i].idx};
    }
    void setMin(int l, int r, pii v)
    {
        setMin(l, r, v, 1, 0, size);
    }
    void setMin(int l, int r, pii v, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
        {
            arr[x] = min(arr[x], v);
            return;
        }
        if (r <= lx || rx <= l)
            return;
        int m = (lx + rx) / 2;
        setMin(l, r, v, 2 * x, lx, m);
        setMin(l, r, v, 2 * x + 1, m, rx);
    }
    pii queryMin(int i) { return queryMin(i, 1, 0, size); }
    pii queryMin(int i, int x, int lx, int rx)
    {
        if (rx - lx == 1)
            return arr[x];
        int m = (lx + rx) / 2;
        pii tmp;
        if (i < m)
            tmp = queryMin(i, 2 * x, lx, m);
        else
            tmp = queryMin(i, 2 * x + 1, m, rx);
        return min(tmp, arr[x]);
    }
};

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

    int N, Q;
    cin >> N >> Q;

    vector<event> E(N);
    vpii Eb(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> E[i].s >> E[i].e;
        E[i].idx = i;
        Eb[i] = {E[i].s, E[i].e};
    }

    sort(all(E), [](event a, event b)
         { return a.s < b.s; });
    vi posInSeg(N);
    for (int i = 0; i < N; ++i)
        posInSeg[E[i].idx] = i;
    segtree seg;
    seg.init(E);

    vvi vorg(N, vi(ceil(log2(N)) + 1));

    auto cmp = [&](int a, int b)
    { if (Eb[a].second == Eb[b].second) return Eb[a].first > Eb[b].first; else return Eb[a].second > Eb[b].second; };
    priority_queue<int, vi, decltype(cmp)> pq(cmp);
    for (int i = 0; i < N; ++i)
        pq.push(i);

    int pointerI = 0;
    while (!pq.empty())
    {
        // move border of starts
        int nextBorder = Eb[pq.top()].second;
        while (pointerI < sz(E) && E[pointerI].s <= nextBorder)
            ++pointerI;
        // add correspondinge elements to segtree
        // TODO: I guess there is no need for a second queue todo
        int idx = pq.top();
        pq.pop();
        seg.setMin(0, pointerI, {Eb[idx].first, idx});
        vorg[idx][0] = seg.queryMin(posInSeg[idx]).second;
    }
    for (int j = 1; j < sz(vorg[0]); ++j)
        for (int i = 0; i < N; ++i)
            vorg[i][j] = vorg[vorg[i][j - 1]][j - 1];

    for (int q = 0, s, e; q < Q; ++q)
    {
        cin >> s >> e;
        --s, --e;
        if (s == e)
        {
            cout << 0 << "\n";
            continue;
        }
        if (Eb[e].first <= Eb[s].second)
        {
            if (Eb[s].second <= Eb[e].second)
                cout << 1 << "\n";
            else // then (Eb[s].second > Eb[e].second)
                cout << "impossible\n";
            continue;
        }

        int ans = 0;
        int tmp = e;
        for (int j = sz(vorg[tmp]) - 1; j >= 0; --j)
        {
            tmp = vorg[e][j];
            if (Eb[s].second < Eb[tmp].first)
            {
                e = tmp;
                ans += (1 << j);
            }
        }
        tmp = vorg[e][0];
        if (Eb[tmp].first <= Eb[s].second)
            cout << ans + 2 << "\n";
        else
            cout << "impossible\n";
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30