Submission #1100995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100995		andrei_iorgulescu	Event Hopping (BOI22_events)	C++14	20 / 100	198 ms	54744 KiB

events

#include <bits/stdc++.h>

using namespace std;

int n, q;
int s[100005], e[100005];
int minl[200005];
int f[200005];

void normalize()
{
    vector<int> pp;
    map<int, int> norma;
    for (int i = 1; i <= n; i++)
        pp.push_back(s[i]), pp.push_back(e[i]);
    sort(pp.begin(), pp.end());
    int poo = 0;
    for (auto it : pp)
        if (!norma[it])
            norma[it] = ++poo;
    for (int i = 1; i <= n; i++)
        s[i] = norma[s[i]], e[i] = norma[e[i]];
    for (int i = 1; i <= 2 * n; i++)
        minl[i] = i;
    for (int i = 1; i <= n; i++)
        minl[e[i]] = min(minl[e[i]], s[i]);
}

pair<int, int> aint[800005];///val, pos

void build(int nod, int l, int r)
{
    if (l == r)
    {
        aint[nod] = {minl[l], l};
        return;
    }
    int mij = (l + r) / 2;
    build(2 * nod, l, mij);
    build(2 * nod + 1, mij + 1, r);
    aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
}

pair<int, int> query(int nod, int l, int r, int st, int dr)
{
    if (r < st or dr < l)
        return {1e9, 0};
    else if (st <= l and r <= dr)
        return aint[nod];
    int mij = (l + r) / 2;
    return min(query(2 * nod, l, mij, st, dr), query(2 * nod + 1, mij + 1, r, st, dr));
}

int lg[200005];
int bl[20][200005], bl1[20][200005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> s[i] >> e[i];
    normalize();
    build(1, 1, 2 * n);
    for (int i = 1; i <= 2 * n; i++)
        f[i] = query(1, 1, 2 * n, minl[i], i).second;
    for (int i = 2; i <= 2 * n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= 2 * n; i++)
        bl[0][i] = f[i];
    for (int j = 1; j <= lg[2 * n]; j++)
        for (int i = 1; i <= 2 * n; i++)
            bl[j][i] = bl[j - 1][bl[j - 1][i]];
    for (int i = 1; i <= 2 * n; i++)
        bl1[0][i] = i;
    for (int j = 1; j <= lg[2 * n]; j++)
        for (int i = 1; i <= 2 * n; i++)
            bl1[j][i] = bl[j - 1][bl1[j - 1][i]];
    for (int i = 1; i <= q; i++)
    {
        int x, y;
        cin >> x >> y;
        int xx = x, yy = y;
        if (x == y)
        {
            cout << "0\n";
            continue;
        }
        x = e[x], y = e[y];
        swap(x, y);
        if (x < y)
            cout << "impossible\n";
        else
        {
            int xs = x, ys = y;
            int ans = 1;
            for (int pas = lg[2 * n]; pas >= 0; pas--)
            {
                if (minl[bl1[pas][x]] > y)
                    ans += (1 << pas), x = bl[pas][x];
            }
            if (minl[x] > y)
                cout << "impossible\n";
            else
            {
                if (s[yy] == minl[xs])
                    cout << ans << '\n';
                else
                {
                    ///maybe ans + 1?
                    x = query(1, 1, 2 * n, s[yy], xs).second;
                    int ans2 = ans;
                    ans = 2;
                    for (int pas = lg[2 * n]; pas >= 0; pas--)
                    {
                        if (minl[bl1[pas][x]] > y)
                            ans += (1 << pas), x = bl[pas][x];
                    }
                    if (minl[x] > y)
                        cout << ans2 + 1 << '\n';
                    else
                        cout << min(ans2 + 1, ans) << '\n';
                }
            }
        }
    }
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:97:25: warning: unused variable 'ys' [-Wunused-variable]
   97 |             int xs = x, ys = y;
      |                         ^~
events.cpp:85:13: warning: unused variable 'xx' [-Wunused-variable]
   85 |         int xx = x, yy = y;
      |             ^~

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