oj.uz

Submission #577668

# Submission time Handle Problem Language Result Execution time Memory
577668 2022-06-15T07:46:24 Z kingfran1907 Event Hopping (BOI22_events) C++14
10 / 100
 1365 ms 51928 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;

const int maxn = 2e5+10;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, q;
pair<int, int> s[maxn];
vector< int > v;
int dp[30][maxn];
int mini[maxn];
int tour[logo][treesiz];

void update(int ind, int x, int val) {
	x += off;
	tour[ind][x] = val;
	
	x /= 2;
	while (x) tour[ind][x] = min(tour[ind][x * 2], tour[ind][x * 2 + 1]), x /= 2;
}

int query(int ind, int a, int b, int l, int r, int node) {
	if (l > b || r < a) return inf;
	if (l >= a && r <= b) return tour[ind][node];
	
	int mid = (l + r) / 2;
	return min(query(ind, a, b, l, mid, node * 2), query(ind, a, b, mid + 1, r, node * 2 + 1));
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		s[i] = {a, b};
		v.push_back(a);
		v.push_back(b);
	}
	
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	for (int i = 0; i < v.size(); i++) mini[i] = i;
	for (int i = 0; i < n; i++) {
		s[i].X = lower_bound(v.begin(), v.end(), s[i].X) - v.begin();
		s[i].Y = lower_bound(v.begin(), v.end(), s[i].Y) - v.begin();
		mini[s[i].Y] = min(mini[s[i].Y], s[i].X);
	}
	
	for (int i = 0; i < v.size(); i++) {
		dp[0][i] = mini[i];
		//printf("mini %d --> %d\n", i, mini[i]);
	}
	for (int i = 1; i < logo; i++) {
		for (int j = 0; j < v.size(); j++) update(i - 1, j, dp[i - 1][j]);
		for (int j = 0; j < v.size(); j++) {
			dp[i][j] = query(i - 1, dp[i - 1][j], j, 0, off - 1, 1);
		}
	}
	for (int i = 0; i < v.size(); i++) update(logo - 1, i, dp[logo - 1][i]);
	
	while (q--) {
		int a, b;
		scanf("%d%d", &a, &b); a--, b--;
		if (s[a].Y > s[b].Y) {
			printf("impossible\n");
			continue;
		}
		if (a == b) {
			printf("0\n");
			continue;
		}
		int ca = a, cb = b;
		
		int sol = inf;
		int dis = 0;
		b = s[b].Y;
		a = s[a].Y;
		for (int i = logo - 1; i >= 0; i--) {
			if (dp[i][b] > a) b = dp[i][b], dis += (1 << i);
			//printf("debug: %d %d\n", a, b);
		}
		if (mini[b] <= a)
			sol = min(sol, dis + 2);
		else {
			printf("impossible\n");
			continue;
		}
		
		dis = 0;
		b = s[cb].Y;
		int l = s[cb].X;
		for (int i = logo - 1; i >= 0; i--) {
			int tren = query(i, l, b, 0, off - 1, 1);
			if (tren > a) l = tren, dis += (1 << i);
			//printf("debug: %d %d %d\n", a, l, b);
		}
		if (l <= a) sol = min(sol, dis + 1);
		if (query(0, l, b, 0, off - 1, 1) <= a) sol = min(dis + 2, sol);
		if (sol >= inf) printf("impossible\n");
		else printf("%d\n", sol);
	}
	return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 0; i < v.size(); i++) mini[i] = i;
      |                  ~~^~~~~~~~~~
events.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
events.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int j = 0; j < v.size(); j++) update(i - 1, j, dp[i - 1][j]);
      |                   ~~^~~~~~~~~~
events.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int j = 0; j < v.size(); j++) {
      |                   ~~^~~~~~~~~~
events.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int i = 0; i < v.size(); i++) update(logo - 1, i, dp[logo - 1][i]);
      |                  ~~^~~~~~~~~~
events.cpp:78:7: warning: unused variable 'ca' [-Wunused-variable]
   78 |   int ca = a, cb = b;
      |       ^~
events.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
events.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
events.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d%d", &a, &b); a--, b--;
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1121 ms 27864 KB Output is correct
3 Correct 1273 ms 27640 KB Output is correct
4 Correct 1184 ms 27608 KB Output is correct
5 Correct 1231 ms 30132 KB Output is correct
6 Correct 1365 ms 32184 KB Output is correct
7 Correct 1229 ms 33132 KB Output is correct
8 Correct 991 ms 51928 KB Output is correct
9 Correct 878 ms 51844 KB Output is correct
10 Correct 838 ms 27964 KB Output is correct
11 Correct 962 ms 37412 KB Output is correct
12 Correct 455 ms 28124 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 6 ms 1776 KB Output is correct
4 Correct 6 ms 1748 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Incorrect 6 ms 1748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 6 ms 1776 KB Output is correct
4 Correct 6 ms 1748 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Incorrect 6 ms 1748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 6 ms 1776 KB Output is correct
4 Correct 6 ms 1748 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Incorrect 6 ms 1748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1278 ms 27724 KB Output is correct
2 Correct 1286 ms 27632 KB Output is correct
3 Correct 1200 ms 27700 KB Output is correct
4 Correct 860 ms 51820 KB Output is correct
5 Correct 946 ms 27980 KB Output is correct
6 Incorrect 1028 ms 51820 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1121 ms 27864 KB Output is correct
3 Correct 1273 ms 27640 KB Output is correct
4 Correct 1184 ms 27608 KB Output is correct
5 Correct 1231 ms 30132 KB Output is correct
6 Correct 1365 ms 32184 KB Output is correct
7 Correct 1229 ms 33132 KB Output is correct
8 Correct 991 ms 51928 KB Output is correct
9 Correct 878 ms 51844 KB Output is correct
10 Correct 838 ms 27964 KB Output is correct
11 Correct 962 ms 37412 KB Output is correct
12 Correct 455 ms 28124 KB Output is correct
13 Correct 1 ms 1620 KB Output is correct
14 Correct 1 ms 1620 KB Output is correct
15 Correct 6 ms 1776 KB Output is correct
16 Correct 6 ms 1748 KB Output is correct
17 Correct 6 ms 1748 KB Output is correct
18 Incorrect 6 ms 1748 KB Output isn't correct
19 Halted 0 ms 0 KB -