Submission #1173579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173579		pinbu	Event Hopping (BOI22_events)	C++20	100 / 100	171 ms	44552 KiB

events

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

const int N = 100005;
void mini(array<int, 2> &X, array<int, 2> Y) {if (X > Y) X = Y;}

int n, q;
int num = -1;
array<int, 2> a[N];
int comp[N << 1];
array<int, 2> SpT[N << 1][18];
int prv[N][17], cost[N][17];

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n >> q;
    for (int i = 1, l, r; i <= n; i++) {
    	cin >> l >> r;
    	a[i] = {l, r};
    	comp[++num] = l;
    	comp[++num] = r;
    }
    sort(comp, comp + 2 * n);
    num = unique(comp, comp + 2 * n) - comp;
    for (int i = 1; i <= num; i++) {
    	SpT[i][0] = {N << 2, N << 2};
    }
    for (int i = 1; i <= n; i++) {
    	a[i][0] = lower_bound(comp, comp + num, a[i][0]) - comp + 1;
    	a[i][1] = lower_bound(comp, comp + num, a[i][1]) - comp + 1;
    	mini(SpT[a[i][1]][0], {a[i][0], i});
    }
    for (int k = 1; k < 18; k++) {
    	for (int i = 1; i + (1 << k) - 1 <= num; i++) {
    		SpT[i][k] = min(SpT[i][k - 1], SpT[i + (1 << (k - 1))][k - 1]);
    	}
    }
    auto gtmin = [&] (int l, int r) {
    	int k = __lg(r - l + 1);
    	return min(SpT[l][k], SpT[r - (1 << k) + 1][k])[1];
    };
    for (int i = 1; i <= n; i++) {
    	prv[i][0] = gtmin(a[i][0], a[i][1]);
    	cost[i][0] = i != prv[i][0];
    }
    for (int k = 1; k < 17; k++) {
    	for (int i = 1; i <= n; i++) {
    		prv[i][k] = prv[prv[i][k - 1]][k - 1];
    		cost[i][k] = cost[i][k - 1] + cost[prv[i][k - 1]][k - 1];
    	}
    }
    
    while (q--) {
    	int s, e; cin >> s >> e;
    	if (s == e) {
    		cout << "0\n";
    		continue;
    	}
    	int ans = 0;
    	for (int k = 16; k >= 0; k--) {
    		if (a[prv[e][k]][0] > a[s][1]) {
    			ans += cost[e][k];
    			e = prv[e][k];
    		}
    	}
    	if (a[e][0] <= a[s][1] && a[s][1] <= a[e][1]) {
    		cout << ans + 1 << '\n';
    		continue;
    	}
    	ans += cost[e][0];
    	e = prv[e][0];
    	if (a[e][0] <= a[s][1] && a[s][1] <= a[e][1]) {
    		cout << ans + 1 << '\n';
    		continue;
    	} 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