Submission #673943

#	Time	Username	Problem	Language	Result	Execution time	Memory
673943		stanislavpolyn	Event Hopping (BOI22_events)	C++17	25 / 100	1585 ms	10060 KiB

events

#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pw(x) (1LL << (x))

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? a = b, 1 : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? a = b, 1 : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 1e5 + 5;

int n, q;
pii a[N];

ve<int> order;

int to[N];
int d[N];
ve<pii> Q[N];
int ans[N];
bool subtask1 = 1;

pii get(int v) {
    if (to[v] == v) {
        return {v, 0};
    } else {
        pii p = get(to[v]);
        p.se += d[v];
        to[v] = p.fi;
        d[v] = p.se;
        return {p.fi, p.se};
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> q;

//    subtask1 &= n > 5000 || q > 100;

    fr (i, 1, n) {
        cin >> a[i].fi >> a[i].se;
        order.pb(i);
    }

    fr (i, 1, q) {
        int s, e;
        cin >> s >> e;

        if (s == e) {
            ans[i] = 0;
            continue;
        }

        if (a[s].se >= a[e].fi && a[s].se <= a[e].se) {
            ans[i] = 1;
            continue;
        }

        if (a[s].se > a[e].se) {
            ans[i] = -1;
            continue;
        }
        Q[e].pb({s, i});
    }


    sort(all(order), [](int i, int j) {
        return a[i].se < a[j].se || (a[i].se == a[j].se && a[i].fi < a[j].fi);
    });

    fr (i, 1, n) {
        to[i] = i;
        d[i] = 0;
    }

    fr (idx, 0, sz(order) - 1) {
        int i = order[idx];

//        cout << a[i].fi << " " << a[i].se << "\n";

        rf (ptr, idx - 1, 0) {

            int j = order[ptr];
//            subtask1 &= to[j] == j;
            subtask1 &= ptr >= idx - 2;

            if (a[j].se < a[i].fi) {
                break;
            }
            to[j] = i;
            d[j] = 1;
        }

        fe (cur, Q[i]) {

            if (subtask1) {
                auto p = get(cur.fi);

                if (p.fi != i) {
                    ans[cur.se] = -1;
                } else {
                    ans[cur.se] = p.se;
                }
            } else {
                int v = cur.fi;
                int sum = 0;
                while (to[v] != v) {
                    sum += d[v];
                    v = to[v];
                }
                if (v == i) {
                    ans[cur.se] = sum;
                } else {
                    ans[cur.se] = -1;
                }
            }
        }
    }

    fr (i, 1, q) {
//      	assert(ans[i] <= 1);
        if (ans[i] == -1) {
            cout << "impossible\n";
        } else {
            cout << ans[i] << "\n";
        }
    }

    return 0;
}

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