oj.uz

Submission #673917

# Submission time Handle Problem Language Result Execution time Memory
673917 2022-12-22T11:47:42 Z stanislavpolyn Event Hopping (BOI22_events) C++17
10 / 100
 72 ms 12236 KB 
#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];

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;

    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].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];

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

            to[j] = i;
            d[j] = 1;
        }

        fe (cur, Q[i]) {
//            int v = cur.fi;
//            int sum = 0;
//            while (to[v] != v) {
//                sum += d[v];
//                v = to[v];
//            }
            auto p = get(cur.fi);

            if (p.fi != i) {
                ans[cur.se] = -1;
            } else {
                ans[cur.se] = p.se;
            }
        }
    }

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

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 57 ms 9552 KB Output is correct
3 Correct 72 ms 9836 KB Output is correct
4 Correct 68 ms 7076 KB Output is correct
5 Correct 60 ms 9608 KB Output is correct
6 Correct 55 ms 9200 KB Output is correct
7 Correct 54 ms 9184 KB Output is correct
8 Correct 50 ms 7116 KB Output is correct
9 Correct 55 ms 7132 KB Output is correct
10 Correct 59 ms 7084 KB Output is correct
11 Correct 58 ms 7132 KB Output is correct
12 Correct 35 ms 6984 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 9648 KB Output is correct
2 Correct 60 ms 9816 KB Output is correct
3 Correct 59 ms 7160 KB Output is correct
4 Correct 48 ms 7244 KB Output is correct
5 Correct 59 ms 7040 KB Output is correct
6 Runtime error 68 ms 12236 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 57 ms 9552 KB Output is correct
3 Correct 72 ms 9836 KB Output is correct
4 Correct 68 ms 7076 KB Output is correct
5 Correct 60 ms 9608 KB Output is correct
6 Correct 55 ms 9200 KB Output is correct
7 Correct 54 ms 9184 KB Output is correct
8 Correct 50 ms 7116 KB Output is correct
9 Correct 55 ms 7132 KB Output is correct
10 Correct 59 ms 7084 KB Output is correct
11 Correct 58 ms 7132 KB Output is correct
12 Correct 35 ms 6984 KB Output is correct
13 Runtime error 4 ms 5204 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -