oj.uz

Submission #612642

# Submission time Handle Problem Language Result Execution time Memory
612642 2022-07-29T18:59:19 Z M_W Event Hopping (BOI22_events) C++17
20 / 100
 265 ms 39776 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
using namespace std;
array<int, 3> a[100001];
vector<int> v;
map<int, int> mp;
int idx[100001], up[100001][21], dist[100001][21], A[100001];
ii q[200001];
vector<array<int, 3>> sorted_q;
bool mark[200002];

ii t[200002 << 2];

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v] = {INT_MAX, tl};
		return;
	}
	int tm = (tl + tr) >> 1;
	
	build(v * 2, tl, tm); build(v * 2 + 1, tm + 1, tr);
	t[v] = {INT_MAX, tl};
}

void ins(int v, int tl, int tr, int pos, int val, int realpos){
	if(tl == realpos && tr == realpos){
		if(t[v].first > val) t[v] = {val, pos};
		return;
	}
	int tm = (tl + tr) >> 1;
	if(realpos <= tm) ins(v * 2, tl, tm, pos, val, realpos);
	else ins(v * 2 + 1, tm + 1, tr, pos, val, realpos);
	
	if(t[v * 2].first < t[v * 2 + 1].first || (t[v * 2].first == t[v * 2 + 1].first && t[v * 2].second < t[v * 2 + 1].second)) t[v] = t[v * 2];
	else t[v] = t[v * 2 + 1];
}

ii query(int v, int tl, int tr, int l, int r){
	if(l > r) return {INT_MAX, 1};
	if(tl == l && tr == r) return t[v];
	int tm = (tl + tr) >> 1;
	
	ii left = query(v * 2, tl, tm, l, min(r, tm));
	ii right = query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
	
	if(left.first < right.first || (left.first == right.first && left.second < right.second)) return left;
	return right;
}

int main(){
	int N, Q, cnt = 0;
	scanf("%d %d", &N, &Q);
	for(int i = 1; i <= N; i++){
		scanf("%d %d", &a[i][1], &a[i][0]); a[i][2] = i;
		v.push_back(a[i][0]); v.push_back(a[i][1]);
	}
	sort(a + 1, a + N + 1); sort(v.begin(), v.end());
	for(auto x : v){
		if(mp.find(x) == mp.end()) mp[x] = ++cnt;
	}
	
	build(1, 1, cnt);
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	for(int i = 1; i <= N; i++){
		a[i][0] = mp[a[i][0]];
		a[i][1] = mp[a[i][1]];
		
		swap(a[i][0], a[i][1]);
		idx[a[i][2]] = i;
	}
	for(int i = 1, u, v; i <= Q; i++){
		scanf("%d %d", &u, &v);
		q[i] = {u, v};
		
		int st = a[idx[v]][0], ed = a[idx[v]][1];
		sorted_q.push_back({idx[v], ed, i});
	}
	sort(sorted_q.begin(), sorted_q.end());
	int idx1 = 0, idx2 = 1;
	for(int i = 1; i <= cnt; i++){
		while(idx1 < Q && sorted_q[idx1][1] == i){
			int query_pos = sorted_q[idx1][2];
			int u = q[query_pos].first, v = q[query_pos].second;
			
			int us = a[idx[u]][0], ut = a[idx[u]][1];
			int vs = a[idx[v]][0], vt = a[idx[v]][1];
			
			while(idx2 < idx[v] && a[idx2][1] <= i){
				ii res = query(1, 1, cnt, a[idx2][0], a[idx2][1]);
				ins(1, 1, cnt, idx2, a[idx2][0], a[idx2][1]);
				
				if(res.first == INT_MAX) up[idx2][0] = idx2;
				else{
					up[idx2][0] = res.second; dist[idx2][0] = 1;
				}
				
				// printf("%d %d : %d %d\n", a[idx2][0], a[idx2][1], res.first, res.second);
				
				for(int j = 1; j <= 20; j++){
					up[idx2][j] = up[up[idx2][j - 1]][j - 1];
					dist[idx2][j] = dist[idx2][j - 1] + dist[up[idx2][j - 1]][j - 1];
				}
				idx2++;
			}
			
			ii res = query(1, 1, cnt, vs, vt);
			int start = res.first == INT_MAX ? idx[v] : res.second;
			
			// printf("%d %d, start = %d %d\n", vs, vt, res.first, res.second, start);
			
			int ans = 1;
			for(int j = 20; j >= 0; j--){
				if(up[start][j] > idx[u]){
					ans += dist[start][j];
					start = up[start][j];
				}
			}
			
			if(start > idx[u]){
				ans += dist[start][0];
				start = up[start][0];	
			}

			// printf("!start = %d\n", start);

			A[query_pos] = (start <= idx[u] && idx[u] <= idx[v] && res.first != INT_MAX) ? ans : -1;
			if(idx[u] == idx[v]) A[query_pos] = 0;
			
			idx1++;
		}
	}
	for(int i = 1; i <= Q; i++){
		if(A[i] == -1) printf("impossible\n");
		else printf("%d\n", A[i]);
	}
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:75:7: warning: unused variable 'st' [-Wunused-variable]
   75 |   int st = a[idx[v]][0], ed = a[idx[v]][1];
      |       ^~
events.cpp:85:8: warning: unused variable 'us' [-Wunused-variable]
   85 |    int us = a[idx[u]][0], ut = a[idx[u]][1];
      |        ^~
events.cpp:85:27: warning: unused variable 'ut' [-Wunused-variable]
   85 |    int us = a[idx[u]][0], ut = a[idx[u]][1];
      |                           ^~
events.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d %d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d %d", &a[i][1], &a[i][0]); a[i][2] = i;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 188 ms 29536 KB Output is correct
3 Correct 199 ms 29560 KB Output is correct
4 Correct 213 ms 29516 KB Output is correct
5 Correct 210 ms 30128 KB Output is correct
6 Correct 206 ms 30420 KB Output is correct
7 Correct 201 ms 30608 KB Output is correct
8 Correct 217 ms 36796 KB Output is correct
9 Correct 218 ms 39776 KB Output is correct
10 Correct 224 ms 32960 KB Output is correct
11 Incorrect 227 ms 36860 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 29492 KB Output is correct
2 Correct 204 ms 29536 KB Output is correct
3 Correct 212 ms 29468 KB Output is correct
4 Correct 241 ms 36688 KB Output is correct
5 Correct 216 ms 29828 KB Output is correct
6 Correct 265 ms 36380 KB Output is correct
7 Correct 261 ms 36416 KB Output is correct
8 Correct 253 ms 36484 KB Output is correct
9 Correct 172 ms 32528 KB Output is correct
10 Correct 233 ms 36128 KB Output is correct
11 Correct 239 ms 35776 KB Output is correct
12 Correct 232 ms 36048 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 188 ms 29536 KB Output is correct
3 Correct 199 ms 29560 KB Output is correct
4 Correct 213 ms 29516 KB Output is correct
5 Correct 210 ms 30128 KB Output is correct
6 Correct 206 ms 30420 KB Output is correct
7 Correct 201 ms 30608 KB Output is correct
8 Correct 217 ms 36796 KB Output is correct
9 Correct 218 ms 39776 KB Output is correct
10 Correct 224 ms 32960 KB Output is correct
11 Incorrect 227 ms 36860 KB Output isn't correct
12 Halted 0 ms 0 KB -