Submission #698103

#	Time	Username	Problem	Language	Result	Execution time	Memory
698103		Duy_e	Event Hopping (BOI22_events)	C++14	0 / 100	2 ms	340 KiB

events

#include <bits/stdc++.h>
#define pii pair <int, int>
#define st first
#define nd second
#define e second
#define s first
#define rep(i, n, m) for (int i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (int i = (n); i >= (m); i --)
using namespace std;
const long long N = 2e5 + 5;
int n, q, sp[20][N], nxt[20][N];
pii a[N];

vector <int> cmp;

int mini(int i, int j) {
    if (i == 0) return j;
    if (j == 0) return i;
    if (a[i].st < a[j].st) return i;
    return j;
}

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

    freopen("events.inp", "r", stdin);
    freopen("events.out", "w", stdout);

    cin >> n >> q;
    rep(i, 1, n) {
        cin >> a[i].st >> a[i].nd;
        cmp.push_back(a[i].st);
        cmp.push_back(a[i].nd);
    }

    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());

    auto find = [&] (int x) {
        return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
    };

    rep(i, 1, n) {
        a[i].st = find(a[i].st);
        a[i].nd = find(a[i].nd);

        if (sp[0][a[i].nd] == 0)
            sp[0][a[i].nd] = i;
        else
            sp[0][a[i].nd] = mini(sp[0][a[i].nd], i);
    }

    rep(i, 1, 19) rep(j, 1, 2 * n)
        if (j + (1 << (i - 1)) <= 2 * n)
            sp[i][j] = mini(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);

    auto get = [&] (int l, int r) {
        int k = log2(r - l + 1);
        return mini(sp[k][l], sp[k][r - (1 << k) + 1]);
    };

    rep(i, 1, n) {
        int u = get(a[i].st, a[i].nd);
        nxt[0][i] = u;
//        cout << i << ' ' << u << '\n';
    }

    rep(i, 1, 19) rep(j, 1, n)
        nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];

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

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

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

        int ans = 0;
        rrep(i, 19, 0) {
            int x = nxt[i][v];
            if (a[u].e < a[x].s) {
                ans += 1 << i;
                v = x;
            }
        }

        if (a[v].s <= a[u].e && a[u].e <= a[v].e) ans ++;
        else v = nxt[0][v], ans += 2;
        if (a[v].s <= a[u].e && a[u].e <= a[v].e)
            cout << ans << '\n';
        else
            cout << "impossible\n";
    }

    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen("events.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen("events.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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