oj.uz

Submission #1085664

# Submission time Handle Problem Language Result Execution time Memory
1085664 2024-09-08T14:35:07 Z djs100201 Event Hopping (BOI22_events) C++17
20 / 100
 218 ms 32068 KB 
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 1e5 + 10, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll S[n_], E[n_], par[n_][20], rev[n_], rev2[n_];
bool cmp(ll x, ll y) {
    if (E[x] ^ E[y]) return E[x] < E[y];
    return S[x] < S[y];
}
bool cmp2(ll x, ll y) { return S[x] < S[y]; }
class seg {
   public:
    vector<ll> tree;
    ll base;
    seg(int n) {
        for (base = 1; base <= n; base *= 2);
        // 0~n쓰겠다
        tree.resize(n * 4 + 4);
        for (int i = 0; i < tree.size(); i++) tree[i] = inf;
    }
    ll f(ll l, ll r) {
        l += base, r += base;
        ll ret = inf;
        while (l <= r) {
            if (l % 2) ret = min(ret, tree[l++]);
            if (!(r % 2)) ret = min(ret, tree[r--]);
            l /= 2, r /= 2;
        }
        return ret;
    }
    void update(ll i, ll v) {
        i += base;
        tree[i] = min(tree[i], v);
        i /= 2;
        while (i) {
            tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
            i /= 2;
        }
    }
};
void solve() {
    ll Q;
    cin >> n >> Q;
    vector<ll> T, idx, idx2;
    for (int i = 1; i <= n; i++) {
        cin >> S[i] >> E[i];
        T.push_back(S[i]), T.push_back(E[i]);
        idx.push_back(i);
    }
    sort(all(idx), cmp2), sort(all(T)), T.erase(unique(all(T)), T.end());
    seg ST(2 * n + 1);
    for (int i = 0; i < n; i++) {
        rev[idx[i]] = i;
        ll a = lower_bound(all(T), E[idx[i]]) - T.begin();
        ST.update(a, i);
    }
    for (int i = 0; i < n; i++) {
        ll l = lower_bound(all(T), S[idx[i]]) - T.begin(), r = lower_bound(all(T), E[idx[i]]) - T.begin();
        par[i][0] = ST.f(l, r);
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            par[i][j] = min(par[i][j - 1], par[par[i][j - 1]][j - 1]);
        }
    }
    while (Q--) {
        cin >> x >> y;
        if (x == y) {
            cout << "0" << '\n';
            continue;
        }
        x = rev[x], y = rev[y];
        if (S[idx[y]] <= E[idx[x]] && E[idx[x]] <= E[idx[y]]) {
            cout << "1" << '\n';
            continue;
        }
        ll l = 0, r = n;
        ans = inf;
        while (l <= r) {
            ll mid = (l + r) / 2, now = y, cost = mid;
            for (int i = 19; i >= 0; i--) {
                if (cost >= (1ll << i)) {
                    cost -= (1ll << i);
                    now = par[now][i];
                }
            }
            if (S[idx[now]] <= E[idx[x]]) {
                ans = min(ans, mid);
                r = mid - 1;
            } else
                l = mid + 1;
        }
        ll now = y, cost = ans;
        for (int i = 19; i >= 0; i--) {
            if (cost >= (1ll << i)) {
                cost -= (1ll << i);
                now = par[now][i];
            }
        }
        assert(now != x);
        if (S[idx[now]] < S[idx[x]] || S[idx[now]] > E[idx[x]])
            cout << "impossible" << '\n';
        else
            cout << ans + 1 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // cin >> tc;
    while (tc--) solve();
};

Compilation message

events.cpp: In constructor 'seg::seg(int)':
events.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int i = 0; i < tree.size(); i++) tree[i] = inf;
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 128 ms 31304 KB Output is correct
3 Correct 158 ms 31296 KB Output is correct
4 Correct 163 ms 31300 KB Output is correct
5 Incorrect 149 ms 31480 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 744 KB Output is correct
6 Incorrect 1 ms 600 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 744 KB Output is correct
6 Incorrect 1 ms 600 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 744 KB Output is correct
6 Incorrect 1 ms 600 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 31300 KB Output is correct
2 Correct 160 ms 31432 KB Output is correct
3 Correct 162 ms 31364 KB Output is correct
4 Correct 122 ms 31916 KB Output is correct
5 Correct 218 ms 31808 KB Output is correct
6 Correct 193 ms 31764 KB Output is correct
7 Correct 214 ms 31824 KB Output is correct
8 Correct 161 ms 32068 KB Output is correct
9 Correct 77 ms 30016 KB Output is correct
10 Correct 131 ms 31552 KB Output is correct
11 Correct 117 ms 31300 KB Output is correct
12 Correct 145 ms 31560 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 128 ms 31304 KB Output is correct
3 Correct 158 ms 31296 KB Output is correct
4 Correct 163 ms 31300 KB Output is correct
5 Incorrect 149 ms 31480 KB Output isn't correct
6 Halted 0 ms 0 KB -