oj.uz

Submission #1085328

# Submission time Handle Problem Language Result Execution time Memory
1085328 2024-09-08T01:12:21 Z djs100201 Event Hopping (BOI22_events) C++17
20 / 100
 192 ms 32132 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_];
bool cmp(ll x, ll y) {
    if (E[x] ^ E[y]) return E[x] < E[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 = max(ret, tree[l++]);
            if (!(r % 2)) ret = max(ret, tree[r--]);
            l /= 2, r /= 2;
        }
        return ret;
    }
    void update(ll i, ll v) {
        i += base;
        tree[i] = max(tree[i], v);
        i /= 2;
        while (i) {
            tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
            i /= 2;
        }
    }
};
void solve() {
    ll Q;
    cin >> n >> Q;
    vector<ll> T, idx;
    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), cmp), 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;
        // cout<<idx[i]<<' '<<i<<endl;
        ll a = lower_bound(all(T), S[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] = 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];
        ll l = 0, r = n;
        ans = inf;
        while (l <= r) {
            ll mid = (l + r) / 2, now = x, cost = mid;
            for (int i = 19; i >= 0; i--) {
                if (cost >= (1ll << i)) {
                    cost -= (1ll << i);
                    now = par[now][i];
                }
            }
            if (E[idx[now]] >= S[idx[y]]) {
                ans = min(ans, mid);
                r = mid - 1;
            } else
                l = mid + 1;
        }
        ll now = x, cost = ans;
        for (int i = 19; i >= 0; i--) {
            if (cost >= (1ll << i)) {
                cost -= (1ll << i);
                now = par[now][i];
            }
        }
        assert(now!=y);
        if (E[idx[now]] < S[idx[y]] || E[idx[now]] > E[idx[y]])
            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:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         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 348 KB Output is correct
2 Correct 122 ms 31652 KB Output is correct
3 Correct 153 ms 31756 KB Output is correct
4 Correct 165 ms 31556 KB Output is correct
5 Incorrect 150 ms 31808 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 1 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 1 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 1 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 31636 KB Output is correct
2 Correct 161 ms 31672 KB Output is correct
3 Correct 173 ms 31772 KB Output is correct
4 Correct 117 ms 32132 KB Output is correct
5 Correct 190 ms 32132 KB Output is correct
6 Correct 192 ms 31812 KB Output is correct
7 Correct 175 ms 31808 KB Output is correct
8 Correct 151 ms 31856 KB Output is correct
9 Correct 77 ms 29880 KB Output is correct
10 Correct 133 ms 31552 KB Output is correct
11 Correct 119 ms 31300 KB Output is correct
12 Correct 130 ms 31428 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 122 ms 31652 KB Output is correct
3 Correct 153 ms 31756 KB Output is correct
4 Correct 165 ms 31556 KB Output is correct
5 Incorrect 150 ms 31808 KB Output isn't correct
6 Halted 0 ms 0 KB -