Submission #612500

#	Time	Username	Problem	Language	Result	Execution time	Memory
612500		M_W	Event Hopping (BOI22_events)	C++17	20 / 100	246 ms	34116 KiB

events

#include <bits/stdc++.h>
#define ii pair<int, int>
using namespace std;
array<int, 3> a[100001];
vector<int> v;
map<int, int> mp;
int idx[100001], up[21][100001], dist[21][100001];

int main(){
	int N, Q, cnt = 0;
	scanf("%d %d", &N, &Q);
	for(int i = 1; i <= N; i++){
		scanf("%d %d", &a[i][0], &a[i][1]); a[i][2] = i;
		v.push_back(a[i][0]); v.push_back(a[i][1]);
	}
	sort(a + 1, a + N + 1); sort(v.begin(), v.end());
	for(auto x : v){
		if(mp.find(x) == mp.end()) mp[x] = ++cnt;
	}
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	for(int i = 1; i <= N; i++){
		a[i][0] = mp[a[i][0]];
		a[i][1] = mp[a[i][1]];
		idx[a[i][2]] = i;
		
		pq.push({a[i][0], -i});
		pq.push({a[i][1], i});
	}
	
	int mx = 0;
	while(!pq.empty()){
		auto [t, i] = pq.top();
		pq.pop();
		
		if(i < 0) mx = max(mx, -i);
		else{
			up[0][abs(i)] = mx; dist[0][abs(i)] = (mx == abs(i)) ? 0 : 1;
			// printf("upp %d %d\n", i, up[0][abs(i)]);
		}
	}
	for(int i = N; i > 0; i--){
		for(int j = 1; j <= 20; j++){
			up[j][i] = up[j - 1][up[j - 1][i]];
			dist[j][i] = dist[j - 1][i] + dist[j - 1][up[j - 1][i]];
		}
	}
	
	for(int i = 1, a, b; i <= Q; i++){
		scanf("%d %d", &a, &b);
		int s = idx[a], t = idx[b];
		// printf(">> %d %d\n", s, t);
		
		if(s == t) printf("0\n");
		else if(t < s) printf("impossible\n");
		else{
			int ans = 0;
			for(int j = 20; j >= 0; j--){
				// printf(">> %d up %d\n", s, up[j][s]);
				if(up[j][s] < t){
					ans += dist[j][s];
					s = up[j][s];
				}
			}
			ans += dist[0][s], s = up[0][s];
			if(s < t) printf("impossible\n");
			else printf("%d\n", ans);
		}
	}
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d %d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d %d", &a[i][0], &a[i][1]); a[i][2] = i;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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