oj.uz

Submission #612500

# Submission time Handle Problem Language Result Execution time Memory
612500 2022-07-29T16:06:32 Z M_W Event Hopping (BOI22_events) C++17
20 / 100
 246 ms 34116 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 177 ms 27832 KB Output is correct
3 Correct 198 ms 29136 KB Output is correct
4 Correct 215 ms 29064 KB Output is correct
5 Incorrect 231 ms 29600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Incorrect 3 ms 852 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Incorrect 3 ms 852 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Incorrect 3 ms 852 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 27836 KB Output is correct
2 Correct 179 ms 29168 KB Output is correct
3 Correct 193 ms 28916 KB Output is correct
4 Correct 213 ms 34116 KB Output is correct
5 Correct 208 ms 29332 KB Output is correct
6 Correct 245 ms 33896 KB Output is correct
7 Correct 246 ms 33852 KB Output is correct
8 Correct 242 ms 34008 KB Output is correct
9 Correct 187 ms 31984 KB Output is correct
10 Correct 214 ms 33592 KB Output is correct
11 Correct 209 ms 33320 KB Output is correct
12 Correct 202 ms 33552 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 177 ms 27832 KB Output is correct
3 Correct 198 ms 29136 KB Output is correct
4 Correct 215 ms 29064 KB Output is correct
5 Incorrect 231 ms 29600 KB Output isn't correct
6 Halted 0 ms 0 KB -