Submission #577679

#	Time	Username	Problem	Language	Result	Execution time	Memory
577679		kingfran1907	Event Hopping (BOI22_events)	C++14	100 / 100	429 ms	333436 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 rmq[logo][logo][maxn];
int pot[maxn];

int query(int ind, int a, int b) {
	int len = b - a + 1;
	int ac = pot[len];
	
	return min(rmq[ind][ac][a], rmq[ind][ac][b - (1 << ac) + 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);
	}
	
	pot[1] = 0;
	for (int i = 2; i < maxn; i++) {
		pot[i] = pot[i - 1];
		if ((i & (i - 1)) == 0) pot[i]++;
	}
	
	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]);
	}
	
	memset(rmq, inf, sizeof rmq);
	for (int i = 1; i < logo; i++) {
		for (int j = 0; j < v.size(); j++) rmq[i - 1][0][j] = dp[i - 1][j];
		for (int j = 1; j < logo; j++)
			for (int k = 0; k < v.size(); k++)
				rmq[i - 1][j][k] = min(rmq[i - 1][j - 1][k], rmq[i - 1][j - 1][k + (1 << (j - 1))]);
		
		for (int j = 0; j < v.size(); j++) {
			dp[i][j] = query(i - 1, dp[i - 1][j], j);
		}
	}
	for (int j = 0; j < v.size(); j++) rmq[logo - 1][0][j] = dp[logo - 1][j];
	for (int j = 1; j < logo; j++)
		for (int k = 0; k < v.size(); k++)
			rmq[logo - 1][j][k] = min(rmq[logo - 1][j - 1][k], rmq[logo - 1][j - 1][k + (1 << (j - 1))]);
	
	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);
			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) <= 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:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 0; i < v.size(); i++) mini[i] = i;
      |                  ~~^~~~~~~~~~
events.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  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++) rmq[i - 1][0][j] = dp[i - 1][j];
      |                   ~~^~~~~~~~~~
events.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    for (int k = 0; k < v.size(); k++)
      |                    ~~^~~~~~~~~~
events.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int j = 0; j < v.size(); j++) {
      |                   ~~^~~~~~~~~~
events.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (int j = 0; j < v.size(); j++) rmq[logo - 1][0][j] = dp[logo - 1][j];
      |                  ~~^~~~~~~~~~
events.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for (int k = 0; k < v.size(); k++)
      |                   ~~^~~~~~~~~~
events.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
events.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
events.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   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: 20 / 20
• Subtask 6: 30 / 30