Submission #1276222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276222		mdobric	Event Hopping (BOI22_events)	C++20	0 / 100	193 ms	31780 KiB

events

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

const int maxn = 100005, off = 262144;
int n, q, a[maxn], b[maxn], go[maxn][17];
set <int> s;
set <int> ::iterator it;
map <int, int> novi;
pair <int, int> T[off * 2 + 5];

pair <int, int> query (int x, int y, int pos, int low, int high){
	if (low >= x and high <= y) return T[pos];
	if (low > y or high < x) return {maxn * 2, -1};
	int mid = (low + high) / 2;
	return min(query(x, y, pos * 2, low, mid), query(x, y, pos * 2 + 1, mid + 1, high));
}

int idi (int x, int p){
	if (go[x][p] != -1) return go[x][p];
	int pola = idi(x, p - 1);
	return go[x][p] = idi(pola, p - 1);
}

int solve (int x, int y){
	if (x == y) return 0;
	if (b[x] > b[y]) return -1;
	if (b[x] >= a[y] and b[x] <= b[y]) return 1;
	//cout << "solve " << x << " " << y << endl;
	int ans = 0;
	for (int i = 16; i >= 0; i--){
		int noviy = idi(y, i);
		if (a[noviy] > b[x]) y = noviy, ans += (1 << i);
	}
	y = go[y][0];
	ans+=2;
	if (b[x] >= a[y] and b[x] <= b[y]) return ans;
	else return -1;
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> q;
	for (int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
		s.insert(a[i]);
		s.insert(b[i]);
	}
	for (int i = off; i < off * 2; i++) T[i].first = maxn * 2, T[i].second = -1;
	memset(go, -1, sizeof go);
	int br = 0;
	for (it = s.begin(); it != s.end(); it++) novi[*it] = br, br++;
	for (int i = 0; i < n; i++){
		a[i] = novi[a[i]];
		b[i] = novi[b[i]];
		if (a[i] < T[off + b[i]].first){	
			T[off + b[i]].first = a[i];
			T[off + b[i]].second = i;
		}
	}
	for (int i = off - 1; i >= 1; i--){
		if (T[i * 2].first < T[i * 2 + 1].first) T[i] = T[i * 2];
		else T[i] = T[i * 2 + 1];
	}
	for (int i = 0; i < n; i++){
		pair <int, int> x = query(a[i], b[i], 1, 0, off - 1);
		if (x.second != -1 and a[x.second] < a[i]) go[i][0] = x.second;
		else go[i][0] = i;
		//cout << i << " " << go[i][0] << endl;
	}
	for (int i = 0; i < q; i++){
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		int ans = solve(x, y);
		if (ans == -1) cout << "IMPOSSIBLE" << "\n";
		else cout << ans << "\n";	
	}

	return 0;
}

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