oj.uz

Submission #1085041

# Submission time Handle Problem Language Result Execution time Memory
1085041 2024-09-07T11:46:19 Z djs100201 Event Hopping (BOI22_events) C++17
20 / 100
 212 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_];
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];
            }
        }
        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 125 ms 31628 KB Output is correct
3 Correct 154 ms 31812 KB Output is correct
4 Correct 171 ms 31556 KB Output is correct
5 Incorrect 153 ms 31812 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 348 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 0 ms 348 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 0 ms 348 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 129 ms 31808 KB Output is correct
2 Correct 162 ms 31808 KB Output is correct
3 Correct 212 ms 31644 KB Output is correct
4 Correct 115 ms 32064 KB Output is correct
5 Correct 192 ms 32068 KB Output is correct
6 Correct 211 ms 31812 KB Output is correct
7 Correct 177 ms 31812 KB Output is correct
8 Correct 160 ms 32068 KB Output is correct
9 Correct 77 ms 30016 KB Output is correct
10 Correct 151 ms 31556 KB Output is correct
11 Correct 122 ms 31128 KB Output is correct
12 Correct 129 ms 31552 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 125 ms 31628 KB Output is correct
3 Correct 154 ms 31812 KB Output is correct
4 Correct 171 ms 31556 KB Output is correct
5 Incorrect 153 ms 31812 KB Output isn't correct
6 Halted 0 ms 0 KB -