Submission #701622

#	Time	Username	Problem	Language	Result	Execution time	Memory
701622		lovrot	Event Hopping (BOI22_events)	C++17	100 / 100	277 ms	36944 KiB

events

#include <cstdio>
#include <vector> 
#include <queue>
#include <stack> 
#include <algorithm> 
#include <cstring>
#include <map>

#define X first
#define Y second
#define pb push_back 

using namespace std; 

typedef pair<int, int> pii; 

const int LOG = 18; 
const int OFF = 1 << LOG; 

int n, t; 
int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF]; 

vector<int> vri, sweep;  
map<int, int> mp; 

int merge(int a, int b) { 
	if(a == -1 || b == -1) return a > -1 ? a : b; 
	return S[a] < S[b] ? a : b; 
}

void update(int a, int val) {
	a += OFF; 
	T[a] = merge(T[a], val); 
	a /= 2;
	while(a) {
		T[a] = merge(T[2 * a], T[2 * a + 1]); 
		a /= 2; 
	}
}

int query(int l, int r, int lo = 0, int hi = OFF, int x = 1) {
	if(r <= lo || hi <= l) return -1;
	if(l <= lo && hi <= r) return T[x];
	int mi = (lo + hi) / 2;
	return merge(query(l, r, lo, mi, 2 * x), query(l, r, mi, hi, 2 * x + 1)); 
}

bool comp(int a, int b) {
	return E[a] == E[b] ? S[a] < S[b] : E[a] < E[b];
}

pii climb(int a, int b) {
	int res = 0; 
	for(int i = LOG - 1; i >= 0; i--) {
		if(up[b][i] == -1) continue; 
		else if(E[a] < S[up[b][i]]) { 
			b = up[b][i]; 
			res += 1 << i; 
		}
	}
	if(E[a] < S[b] && up[b][0] != -1) {
		b = up[b][0]; 
		res++;
	}
	return {b, res}; 
}

int main() {
	memset(up, -1, sizeof(up)); 
	memset(T, -1, sizeof(T));

	scanf("%d%d", &n, &t); 
	for(int i = 0; i < n; i++) {
		scanf("%d%d", S + i, E + i); 
		vri.pb(S[i]);
		vri.pb(E[i]); 
		//vri.pb(E[i] + 1); 
	}
	
	sort(vri.begin(), vri.end());
	vri.erase(unique(vri.begin(), vri.end()), vri.end());  
	
	for(int i = 0; i < (int) vri.size(); i++) mp[vri[i]] = i; 
	
	for(int i = 0; i < n; i++) {
		S[i] = mp[S[i]]; 
		E[i] = mp[E[i]]; 
		//printf("Si = %d Ei = %d\n", S[i] + 1, E[i] + 1);
		sweep.pb(i); 
	}

	sort(sweep.begin(), sweep.end(), comp); 

	for(int i : sweep) {
		up[i][0] = query(S[i], E[i] + 1); 
		update(E[i], i); 
		if(S[i] <= S[up[i][0]]) up[i][0] = -1;
		//printf("UP%d = %d\n", i, up[i][0]);
	}

	for(int j = 1; j < LOG; j++)
		for(int i = 0; i < n; i++)
			if(up[i][j - 1] != -1) up[i][j] = up[up[i][j - 1]][j - 1]; 

	for(int i = 0; i < t; i++) {
		int s, e; 
		scanf("%d%d", &s, &e); 
		//printf("%d %d\n", s, e);
		s--; 
		e--; 
		// if(t >= 20) continue;
		if(e == s) {
			printf("0\n");
		} else if(E[e] < E[s]) {
			printf("impossible\n");  
		} else {
			pii r = climb(s, e); 
			if(S[r.X] <= E[s] && E[s] <= E[r.X]) printf("%d\n", r.Y + 1); 
			else printf("impossible\n");
		}
	}
	return 0; 
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
events.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d%d", S + i, E + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
events.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   scanf("%d%d", &s, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~

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