Submission #624096

#	Time	Username	Problem	Language	Result	Execution time	Memory
624096		ddy888	Event Hopping (BOI22_events)	C++17	100 / 100	257 ms	84484 KiB

events

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops")
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int INF = 1e9, MAXN = 100010;

int n, q;
vector<ti> events; // end, start, index
int st[20][MAXN], order[MAXN];
pi old[MAXN];

struct node { // thanks rs
    int s,e,m;
    pi v;
    node *l,*r;
    node(int S,int E){
        s=S,e=E,m=(s+e)>>1;
        v=pi(INF,0);
        l=r=0;
    }
    void update(int x,pi nval) {
        if(s==e) {
            v = min(v, nval);
            return;
        }
        if(x>m) cr(), r->update(x,nval);
        else cl(), l->update(x,nval);
        v=min(l?l->v:pi(INF,0),r?r->v:pi(INF,0));
    }
    pi rmq(int x,int y) {
        if(s==x&&e==y) return v;
        if(x>m)return r?r->rmq(x,y):pi(INF,0);
        else if(y<=m)return l?l->rmq(x,y):pi(INF,0);
        else return min(l?l->rmq(x,m):pi(INF,0),r?r->rmq(m+1,y):pi(INF,0));
    }
    void cr() { if(!r) r=new node(m+1,e); }
    void cl() { if(!l) l=new node(s,m); }
} *seg;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin.exceptions(ios::badbit | ios::failbit);

    memset(st, -1, sizeof st);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int a, b; cin >> a >> b;
        events.pb({b, a, i});
        old[i] = {a, b};
    }
    sort(events.begin(), events.end());
    seg = new node(1, (int)1e9);
    int cnt = 0;
    for (auto [e, s, id]: events) {
       order[id] = ++cnt;
       pi qq = seg->rmq(s, e);
       if (qq.fi < s) {
           st[0][id] = qq.si;
       }
       seg->update(e, pi(s, id));
    }
    for (int i = 1; i < 20; ++i) {
        for (int j = 1; j <= n; ++j) {
            st[i][j] = st[i - 1][st[i - 1][j]];
        }
    }
    auto check = [&](int i, int j) { 
        return (old[j].fi <= old[i].si && old[i].si <= old[j].si);
    };
    while (q--) {
        int s, e; cin >> s >> e;
        if (s == e) {
            cout << 0 << '\n';
            continue;
        }
        if (check(s, e)) {
            cout << 1 << '\n';
            continue;
        }
        if (old[s].si > old[e].si) {
            cout << "impossible\n";
            continue;
        }
        int node = e, ans = 0;
        for (int i = 19; i >= 0; --i) {
            int pa = st[i][node];
            if (pa == -1 || old[pa].si <= old[s].si || old[pa].fi <= old[s].fi) continue;
            node = pa;
            ans += (1 << i);
        }
        if (check(s, node)) {
            cout << ans + 1 << '\n';
        } else if (check(s, st[0][node])) {
            cout << ans + 2 << '\n';
        } else cout << "impossible\n";
    }
    return 0;
}   

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