Submission #577670

#	Time	Username	Problem	Language	Result	Execution time	Memory
577670		kingfran1907	Event Hopping (BOI22_events)	C++14	50 / 100	1532 ms	51944 KiB

events

#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;
		}*/
		
		int dis = 0;
		b = s[cb].Y;
		int l = s[cb].X;
		a = s[ca].Y;
		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 (stderr)

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: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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30