제출 #1172142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172142		Iskachun	Event Hopping (BOI22_events)	C++20	100 / 100	191 ms	42468 KiB

events

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
# define f first
# define s second
const ll inf = 1e18;
vector<pair<ll,ll>> a;
ll ask (ll l, ll r) {
    ll n = a.size();
    l += n / 2, r += n / 2;
    ll pos, best = inf;
    while (l <= r) {
        if (l % 2 == 1) {
            if (a[l].first < best) best = a[l].first, pos = a[l].second;
            l++;
        }
        if (r % 2 == 0) {
            if (a[r].first < best) best = a[r].first, pos = a[r].second;
            r--;
        }
        l /= 2; r /= 2;
    }
    return pos;
}
void solve () {
    ll n, q; cin >> n >> q;
    vector<pair<ll, ll>> ev(n);
    for (auto &[x, y] : ev) cin >> x >> y;
    vector<ll> num;
    for (auto [x, y] : ev) num.push_back(x), num.push_back(y);
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    map<ll, ll> mp;
    ll m = num.size();
    for (ll i = 0; i < m; i++) mp[num[i]] = i;
    for (auto &[x, y] : ev) x = mp[x], y = mp[y];
    ll k = pow(2, ceil(log2(m)));
    a = vector<pair<ll, ll>> (2 * k, make_pair(inf, -1));
    for (ll i = 0; i < n; i++) {
        if (ev[i].first < a[k + ev[i].second].first) {
            a[k + ev[i].second] = {ev[i].first, i};
        }
    }
    for (ll i = k - 1; i > 0; i--) {
        if (a[2 * i].first < a[2 * i + 1].first) a[i] = a[2 * i];
        else a[i] = a[2 * i + 1];
    }
    ll logn = log2(n);
    vector<vector<ll>> prev2(n, vector<ll> (logn + 1, -1));
    vector<ll> prev(n);
    for (ll i = 0; i < n; i++) {
        prev[i] = ask(ev[i].first, ev[i].second);
        prev2[i][0] = prev[i];
    }
    for (ll i = 1; i <= logn; i++) for (ll j = 0; j < n; j++) {
        prev2[j][i] = prev2[prev2[j][i - 1]][i - 1];
    }
    while (q--) {
        ll s, e; cin >> s >> e; s--, e--;
        if (s == e) {cout << "0\n"; continue;}
        if (ev[s].second > ev[e].second) {cout << "impossible\n"; continue;}
        if (ev[e].first <= ev[s].second and ev[e].second >= ev[s].second) {cout << "1\n"; continue;}
        ll curr = e, cnt = 0;
        for (ll i = logn; i >= 0; i--) {
            ll nxt = prev2[curr][i];
            if (ev[s].second < ev[nxt].first) curr = nxt, cnt += (1 << i);
        }
        curr = prev[curr], cnt++;
        if (ev[s].second >= ev[curr].first) cout << cnt + 1 << '\n';
        else cout << "impossible\n";
    }
}

int main() {
    //freopen("filename.in", "r", stdin), freopen("filename.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; //cin >> t;
    while (t--) solve();

}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30