Submission #970822

#	Time	Username	Problem	Language	Result	Execution time	Memory
970822		kl0989e	Event Hopping (BOI22_events)	C++17	0 / 100	68 ms	19024 KiB

events

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define all(x) (x).begin(),(x).end()

const int maxn=1e5+10;
const int LOG=int(log2(maxn))+1;
int n;
vector<pi> events(maxn);
vi order(maxn);
vi get_ord(maxn);
vector<bool> seen(maxn,0);
vector<vi> table(maxn,vi(LOG,-1));
vi pow2(LOG,1);

void precalc() {
    for (int i=1; i<pow2.size(); i++) {
        pow2[i]=2*pow2[i-1];
    }
}

void dfs(int cur, int prev=-1, bool fd=1) {
    if (seen[cur]) {
        return;
    }
    seen[cur]=1;
    table[cur][0]=prev;
    for (int i=1; i<LOG; i++) {
        if (table[cur][i-1]==-1) {
            break;
        }
        table[cur][i]=table[table[cur][i-1]][i-1];
    }
    if (fd) {
        int end;
        for (end=cur+1; end<n; end++) {
            if (events[order[end]].fi<=events[order[cur]].se && events[order[cur]].se<=events[order[end]].se) {
                continue;
            }
            break;
        }
        dfs(end-1,cur,1);
        for (int i=end-2; i>cur; i--) {
            dfs(i,cur,0);
        }
    }
}

string get_ans(int a, int b) {
    int ans=0;
    for (int i=LOG-1; i>=0; i--) {
        if (table[b][i]>a) {
            b=table[b][i];
            ans+=pow2[i];
        }
    }
    //cout << "temp:" << ans << ' ' << a << ' ' << b << ' ' << order[a] << ' ' << order[b] << '\n';
    if (events[order[a]]==events[order[b]]) {
        return to_string(ans);
    }
    if (events[order[b]].fi<=events[order[a]].se && events[order[a]].se<=events[order[b]].se) {
        return to_string(ans+1);
    }
    return "impossible";

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    precalc();
    int q;
    cin >> n >> q;
    for (int i=0; i<n; i++) {
        cin >> events[i].fi >> events[i].se;
    }
    iota(order.begin(),order.begin()+n,0);
    sort(order.begin(),order.begin()+n,[&](int a, int b){return events[a]<events[b];});
    for (int i=0; i<n; i++) {
        get_ord[order[i]+1]=i;
    }
    dfs(0,-1);
    /*for (int i=0; i<n; i++) {
        cout << i << ": ";
        for (int j=0; j<LOG; j++) {
            cout << table[i][j] << ' ';
        }
        cout << '\n';
    }*/
    int a,b;
    for (int i=0; i<q; i++) {
        cin >> a >> b;
        a=get_ord[a];
        b=get_ord[b];
        if (a>b) {
            cout << "impossible\n";
            continue;
        }
        if (a==b) {
            cout << "0\n";
            continue;
        }
    	cout << get_ans(a,b) << '\n';
    }
    return 0;
}

Compilation message (stderr)

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

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