Submission #653883

#	Time	Username	Problem	Language	Result	Execution time	Memory
653883		couplefire	Event Hopping (BOI22_events)	C++17	100 / 100	380 ms	36192 KiB

events

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

const int N = 1<<17;
const int INF = 0x3f3f3f3f;

int n, q;
pair<int, int> segs[N];
map<int, int> mp;
vector<int> stuff;
vector<pair<int, int>> bruh[N<<1];
int tree[N<<2];
int to[N][20];

void upd(int pos, int val, int tl = 0, int tr = (N<<1)-1, int v = 1) {
    if (tr < pos || tl > pos) {
        return;
    }
    if (tl == tr) {
        tree[v] = min(tree[v], val);
        return;
    }
    int tm = (tl+tr)>>1;
    upd(pos, val, tl, tm, v<<1);
    upd(pos, val, tm+1, tr, v<<1|1);
    tree[v] = min(tree[v<<1], tree[v<<1|1]);
}

int query(int l, int r, int tl = 0, int tr = (N<<1)-1, int v = 1) {
    if (tr < l || tl > r) {
        return INF;
    }
    if (l <= tl && tr <= r) {
        return tree[v];
    }
    int tm = (tl+tr)>>1;
    return min(query(l, r, tl, tm, v<<1), query(l, r, tm+1, tr, v<<1|1));
}

int main() {
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(tree, INF, sizeof tree);
    memset(to, -1, sizeof to);

    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> segs[i].first >> segs[i].second;
        stuff.push_back(segs[i].first);
        stuff.push_back(segs[i].second);
    }
    sort(stuff.begin(), stuff.end());
    stuff.erase(unique(stuff.begin(), stuff.end()), stuff.end());
    for (int i = 0; i < stuff.size(); ++i) {
        mp[stuff[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        segs[i].first = mp[segs[i].first];
        segs[i].second = mp[segs[i].second];
        upd(segs[i].second, segs[i].first);
        bruh[segs[i].first].push_back({segs[i].second, i});
    }
    for (int i = 0; i < (N<<1); ++i) {
        sort(bruh[i].begin(), bruh[i].end());
    }
    for (int i = 0; i < n; ++i) {
        int val = query(segs[i].first, segs[i].second);
        if (val < segs[i].first) {
            to[i][0] = (*lower_bound(bruh[val].begin(), bruh[val].end(), pair<int, int>{segs[i].first, -1})).second;
        }
    }
    for (int i = 1; i < 20; ++i) {
        for (int j = 0; j < n; ++j) {
            if (to[j][i-1] != -1) {
                to[j][i] = to[to[j][i-1]][i-1];
            }
        }
    }
    while (q--) {
        int s, e;
        cin >> s >> e;
        --s, --e;
        if (s == e) {
            cout << 0 << '\n';
            continue;
        }
        if (segs[s].second > segs[e].second) {
            cout << "impossible" << '\n';
            continue;
        }
        if (segs[s].second >= segs[e].first) {
            cout << 1 << '\n';
            continue;
        }
        int ans = 0, cur = e;
        for (int i = 19; i >= 0; --i) {
            if (to[cur][i] != -1 && segs[s].second < segs[to[cur][i]].first) {
                ans += (1<<i);
                cur = to[cur][i];
            }
        }
        if (to[cur][0] != -1) {
            cout << ans+2 << '\n';
        } else {
            cout << "impossible" << '\n';
        }
    }
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < stuff.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

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