oj.uz

Submission #701500

# Submission time Handle Problem Language Result Execution time Memory
701500 2023-02-21T11:17:10 Z lovrot Event Hopping (BOI22_events) C++17
0 / 100
 170 ms 31860 KB 
#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 i = 0; i < n; i++)
		for(int j = 1; j < LOG; j++)
			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(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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20820 KB Output is correct
2 Incorrect 170 ms 31860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20760 KB Output is correct
2 Correct 9 ms 20728 KB Output is correct
3 Incorrect 10 ms 20828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20760 KB Output is correct
2 Correct 9 ms 20728 KB Output is correct
3 Incorrect 10 ms 20828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20760 KB Output is correct
2 Correct 9 ms 20728 KB Output is correct
3 Incorrect 10 ms 20828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 31776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20820 KB Output is correct
2 Incorrect 170 ms 31860 KB Output isn't correct
3 Halted 0 ms 0 KB -