Submission #1094675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094675		not_amir	Event Hopping (BOI22_events)	C++14	100 / 100	166 ms	21296 KiB

events

#include <bits/stdc++.h>
using namespace  std;

typedef pair<int, int> pii;
constexpr int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vector<pair<pii, int>> events(n);
    vector<int> start(n), end(n);
    map<int, int> mp;
    for(int i = 0; i < n; i++) {
        cin >> start[i] >> end[i];
        events[i].first = {end[i], start[i]};
        mp[start[i]] = mp[end[i]] = 1;
        events[i].second = i;
    }
    int t = 0;
    for(auto& [x, cmp] : mp)
        cmp = t++;
    sort(events.begin(), events.end());
    int N = 1 << 32 - __builtin_clz(t - 1);
    vector<pii> st(2 * N, {INF, -1});
    vector<int> parent(n), jump(n), depth(n);
    for(int i = 0; i < n; i++) {
        int e = events[i].first.first, s = events[i].first.second;
        pii ans = {INF, -1};
        for(int l = N + mp[s], r = 2 * N; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ans = min(ans, st[l++]);
            if(r & 1) ans = min(ans, st[--r]);
        }
        int v = events[i].second;
        if(ans.second == -1 || ans.first >= s)
            jump[v] = parent[v] = v;
        else {
            int p = parent[v] = ans.second;
            depth[v] = depth[p] + 1;
            if(depth[p] - depth[jump[p]] == depth[jump[p]] - depth[jump[jump[p]]])
                jump[v] = jump[jump[p]];
            else
                jump[v] = p;
        }
        for(int j = N + mp[e]; j > 0; j >>= 1)
            st[j] = min(st[j], {s, v});
    }
    while(q--) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        int d = depth[y];
        while(!(end[x] >= start[y] && end[x] <= end[y]) && x != y && parent[y] != y && end[y] >= end[x]) {
            if(start[jump[y]] > start[x])
                y = jump[y];
            else
                y = parent[y];
        }
        if(end[x] >= start[y] && end[x] <= end[y])
            cout << (x!=y) + d - depth[y] << '\n';
        else
            cout << "impossible\n";
    }
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for(auto& [x, cmp] : mp)
      |               ^
events.cpp:25:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |     int N = 1 << 32 - __builtin_clz(t - 1);
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~

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