oj.uz

답안 #1085330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1085330 2024-09-08T01:36:05 Z djs100201 Event Hopping (BOI22_events) C++17
30 / 100
 207 ms 32136 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;
        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] = max(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];
        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:61:12: warning: unused variable 'l' [-Wunused-variable]
   61 |         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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 157 ms 31812 KB Output is correct
3 Correct 158 ms 31648 KB Output is correct
4 Correct 165 ms 31640 KB Output is correct
5 Correct 153 ms 32064 KB Output is correct
6 Correct 137 ms 31812 KB Output is correct
7 Correct 129 ms 31880 KB Output is correct
8 Correct 121 ms 32068 KB Output is correct
9 Correct 117 ms 32064 KB Output is correct
10 Correct 196 ms 32020 KB Output is correct
11 Correct 195 ms 32064 KB Output is correct
12 Correct 94 ms 31296 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 31816 KB Output is correct
2 Correct 177 ms 31624 KB Output is correct
3 Correct 167 ms 31768 KB Output is correct
4 Correct 119 ms 32136 KB Output is correct
5 Correct 207 ms 32132 KB Output is correct
6 Correct 190 ms 31812 KB Output is correct
7 Correct 170 ms 31808 KB Output is correct
8 Correct 150 ms 32068 KB Output is correct
9 Correct 72 ms 30020 KB Output is correct
10 Correct 126 ms 31536 KB Output is correct
11 Correct 112 ms 31296 KB Output is correct
12 Correct 134 ms 31560 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 157 ms 31812 KB Output is correct
3 Correct 158 ms 31648 KB Output is correct
4 Correct 165 ms 31640 KB Output is correct
5 Correct 153 ms 32064 KB Output is correct
6 Correct 137 ms 31812 KB Output is correct
7 Correct 129 ms 31880 KB Output is correct
8 Correct 121 ms 32068 KB Output is correct
9 Correct 117 ms 32064 KB Output is correct
10 Correct 196 ms 32020 KB Output is correct
11 Correct 195 ms 32064 KB Output is correct
12 Correct 94 ms 31296 KB Output is correct
13 Correct 0 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 -