Submission #1085437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085437		djs100201	Event Hopping (BOI22_events)	C++17	0 / 100	882 ms	405188 KiB

events

#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_ = 2e5 + 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_], res[n_];
vector<PP> Q[n_];
vector<P> U[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 = min(ret, tree[l++]);
            if (!(r % 2)) ret = min(ret, tree[r--]);
            l /= 2, r /= 2;
        }
        return ret;
    }
    void update(ll i, ll v) {
        i += base;
        tree[i] = min(tree[i], v);
        i /= 2;
        while (i) {
            tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
            i /= 2;
        }
    }
};
//! 주의 0이 lover_bound입니다.
class lazy_seg {
   public:
    vector<ll> tree, lazy, A;
    lazy_seg() {}
    lazy_seg(int n) {
        // 0~n까지 쓰겠다.
        tree.resize(n * 4);
        lazy.resize(n * 4);
        A.resize(n * 4);
    }
    ll init(ll N, ll s, ll e) {
        if (s == e) return tree[N] = A[s];
        ll mid = (s + e) / 2;
        return tree[N] = max(init(N * 2, s, mid), init(N * 2 + 1, mid + 1, e));
    }
    void update_lazy(ll N, ll s, ll e) {
        if (!lazy[N]) return;
        tree[N] = max(tree[N], lazy[N]);
        if (s != e) {
            lazy[N * 2] = max(lazy[N * 2], lazy[N]);
            lazy[N * 2 + 1] = max(lazy[N * 2 + 1], lazy[N]);
        }
        lazy[N] = 0;
    }
    void update(ll N, ll s, ll e, ll l, ll r, ll val) {
        update_lazy(N, s, e);
        if (l > e || r < s) return;
        if (l <= s && e <= r) {
            lazy[N] = val;
            update_lazy(N, s, e);
            return;
        }
        ll mid = (s + e) / 2;
        update(N * 2, s, mid, l, r, val);
        update(N * 2 + 1, mid + 1, e, l, r, val);
        tree[N] = max(tree[N * 2], tree[N * 2 + 1]);
    }
    ll f(ll N, ll s, ll e, ll l, ll r) {
        update_lazy(N, s, e);
        if (l > e || r < s) return 0;
        if (l <= s && e <= r) return tree[N];
        ll mid = (s + e) / 2;
        return max(f(N * 2, s, mid, l, r), f(N * 2 + 1, mid + 1, e, l, r));
    }
};
lazy_seg ST[20];
ll go(ll now, ll x) {
    for (int i = 19; i >= 0; i--) {
        if (x >= (1ll << i)) {
            now = ST[i].f(1, 0, n - 1, now, now);
            x -= (1ll << i);
        }
    }
    return now;
}
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());
    for (int i = 0; i < n; i++) {
        rev[idx[i]] = i;
        ll e = lower_bound(all(T), E[idx[i]]) - T.begin();
        U[e].push_back({S[idx[i]], i});
    }
    for (int i = 0; i < q; i++) {
        cin >> x >> y;
        if (x != y) {
            x = rev[x], y = rev[y];
            ll a = lower_bound(all(T), E[idx[y]]) - T.begin();
            Q[a].push_back({i, {x, y}});
        }
    }
    for (int i = 0; i < 18; i++) {
        lazy_seg T(n);
        for (int j = 0; j < n; j++) T.A[j] = j;
        T.init(1, 0, n - 1);
        ST[i] = T;
    }
    seg ST2(n + 1);
    for (int i = 0; i < n; i++) ST2.update(i, S[idx[i]]);
    for (int i = 0; i < n_; i++) {
        if (U[i].size()) {
            sort(all(U[i]));
            ll s = U[i][0].first, e = T[i], L = inf, R = -inf, l, r;
            l = 0, r = n - 1;
            while (l <= r) {
                ll mid = (l + r) / 2;
                if (E[idx[mid]] <= e) {
                    R = max(R, mid);
                    l = mid + 1;
                } else
                    r = mid - 1;
            }
            for (int j = 0; j < 18; j++) {
                l = 0, r = n - 1;
                ll bef = R;
                while (l <= r) {
                    ll mid = (l + r) / 2;
                    if (E[idx[mid]] >= s) {
                        L = min(L, mid);
                        r = mid - 1;
                    } else
                        l = mid + 1;
                }
                if (L <= R) {
                    ST[j].update(1, 0, n - 1, L, R, U[i][0].second);
                    s = ST2.f(L, R);
                } else
                    break;
            }
        }

        for (auto [x, cur] : Q[i]) {
            ll now = cur.first, cost = 0;
            for (int j = 19; j >= 0; j--) {
                ll val = (1ll << j);
                if (E[idx[go(now, val - 1)]] >= S[idx[cur.second]]) continue;
                cost += val;
                now = go(now, val);
            }
            now = idx[now];
            if (E[now] < S[idx[cur.second]] || E[now] > E[idx[cur.second]])
                res[x] = -1;
            else
                res[x] = cost + 1;
        }
    }
    for (int i = 0; i < q; i++) {
        if (res[i] == -1)
            cout << "impossible";
        else
            cout << res[i];
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // cin >> tc;
    while (tc--) solve();
};

Compilation message (stderr)

events.cpp: In constructor 'seg::seg(int)':
events.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int i = 0; i < tree.size(); i++) tree[i] = inf;
      |                         ~~^~~~~~~~~~~~~
events.cpp: In function 'void solve()':
events.cpp:149:20: warning: unused variable 'bef' [-Wunused-variable]
  149 |                 ll bef = R;
      |                    ^~~

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