oj.uz

Submission #1085329

# Submission time Handle Problem Language Result Execution time Memory
1085329 2024-09-08T01:27:07 Z djs100201 Event Hopping (BOI22_events) C++17
30 / 100
 215 ms 32140 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(0, 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;
      |                         ~~^~~~~~~~~~~~~
events.cpp: In function 'void solve()':
events.cpp:62:12: warning: unused variable 'l' [-Wunused-variable]
   62 |         ll l = lower_bound(all(T), S[idx[i]]) - T.begin(), r = lower_bound(all(T), E[idx[i]]) - T.begin();
      |            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 126 ms 31812 KB Output is correct
3 Correct 164 ms 31808 KB Output is correct
4 Correct 174 ms 31760 KB Output is correct
5 Correct 150 ms 31812 KB Output is correct
6 Correct 136 ms 31812 KB Output is correct
7 Correct 153 ms 31812 KB Output is correct
8 Correct 117 ms 32068 KB Output is correct
9 Correct 116 ms 32068 KB Output is correct
10 Correct 215 ms 32064 KB Output is correct
11 Correct 190 ms 32140 KB Output is correct
12 Correct 98 ms 31388 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 1 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 126 ms 31812 KB Output is correct
2 Correct 181 ms 31624 KB Output is correct
3 Correct 164 ms 31640 KB Output is correct
4 Correct 124 ms 32068 KB Output is correct
5 Correct 201 ms 32068 KB Output is correct
6 Correct 184 ms 31928 KB Output is correct
7 Correct 168 ms 31808 KB Output is correct
8 Correct 145 ms 32068 KB Output is correct
9 Correct 74 ms 29996 KB Output is correct
10 Correct 126 ms 31380 KB Output is correct
11 Correct 116 ms 31164 KB Output is correct
12 Correct 123 ms 31556 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 126 ms 31812 KB Output is correct
3 Correct 164 ms 31808 KB Output is correct
4 Correct 174 ms 31760 KB Output is correct
5 Correct 150 ms 31812 KB Output is correct
6 Correct 136 ms 31812 KB Output is correct
7 Correct 153 ms 31812 KB Output is correct
8 Correct 117 ms 32068 KB Output is correct
9 Correct 116 ms 32068 KB Output is correct
10 Correct 215 ms 32064 KB Output is correct
11 Correct 190 ms 32140 KB Output is correct
12 Correct 98 ms 31388 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Incorrect 1 ms 604 KB Output isn't correct
18 Halted 0 ms 0 KB -