Submission #762102

#	Time	Username	Problem	Language	Result	Execution time	Memory
762102		zsombor	Event Hopping (BOI22_events)	C++17	20 / 100	271 ms	42008 KiB

events

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
struct event {
    int s, e, ind;
    vector <pair <int, int>> Q;
};
 
int n, q;
vector <event> ev;
vector <int> new_ind(1e5 + 1);
//vector <node> sgt(3e5, node());
vector <int> Log(1e5 + 1, 0);
vector <vector <int>> st(2e5, vector<int>(17));
vector <vector <int>> lift(1e5, vector<int>(17));
vector <int> ans;
 
bool srt(event a, event b) {
    if (a.e < b.e) return true;
    if (a.e > b.e) return false;
    return (a.s < b.s ? true : false);
}
 
int bs(int val) {
    int a = -1, b = n - 1, c;
    while (b - a > 1) {
        c = (a + b) / 2;
        (ev[c].e < val ? a = c : b = c);
    }
    return b;
}
 
int mini(int a, int b) {
    return (ev[a].s < ev[b].s ? a : b);
}
 
int range_mini(int l, int r) {
    int j = Log[r - l + 1];
    return mini(st[l][j], st[r - (1 << j) + 1][j]);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> q;
    ev.resize(n);
    ans.resize(q, 0);
    for (int i = 0; i < n; i++) {
        cin >> ev[i].s >> ev[i].e;
        ev[i].ind = i + 1;
    }
    sort(ev.begin(), ev.end(), srt);
    for (int i = 0; i < n; i++) new_ind[ev[i].ind] = i;
 
    int a, b;
    for (int i = 0; i < q; i++) {
        cin >> a >> b;
        a = new_ind[a];
        b = new_ind[b];
        ev[b].Q.push_back({ a,i });
    }
 
    for (int i = 2; i <= 1e5; i++) Log[i] = Log[i / 2] + 1;
    for (int i = 0; i < n; i++) st[i][0] = i;
    for (int i = n; i < 2e5; i++) fill(st[i].begin(), st[i].end(), n - 1);
    for (int j = 1; j < 17; j++) {
        for (int i = 0; i < n; i++) {
            st[i][j] = mini(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        lift[i][0] = bs(ev[i].s);
        for (int j = 1; j < 17; j++) {
            a = range_mini(lift[i][j - 1], i);
            lift[i][j] = lift[a][j - 1];
        }
        for (auto& p : ev[i].Q) {
            a = p.first, b = i;
            if (ev[a].e == ev[b].e) continue;
            if (a > b) { ans[p.second] = (1 << 17); continue; }
            for (int j = 16; j >= 0; j--) {
                if (lift[b][j] <= a) continue;
                b = lift[b][j];
                ans[p.second] += (1 << j);
            }
            ans[p.second]++;
        }
    }
 
    for (int& i : ans) {
        if (i < (1 << 17)) cout << i << endl;
        else cout << "impossible\n";
    }
}

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