oj.uz

Submission #612610

# Submission time Handle Problem Language Result Execution time Memory
612610 2022-07-29T18:15:12 Z M_W Event Hopping (BOI22_events) C++17
20 / 100
 262 ms 39800 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;

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] = 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) 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({ed, st, i});
	}
	sort(sorted_q.begin(), sorted_q.end());
	int idx1 = 0, idx2 = 1;
	for(int i = 1; i <= cnt; i++){
		while(idx2 <= N && 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;
			}
			
			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++;
		}

		while(idx1 < Q && sorted_q[idx1][0] == i){
			// Do something
			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];
			
			ii res = query(1, 1, cnt, vs, vt);
			int start = res.second;

			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];	
			}

			A[query_pos] = (start <= idx[u] && idx[u] <= idx[v]) ? 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:101:8: warning: unused variable 'us' [-Wunused-variable]
  101 |    int us = a[idx[u]][0], ut = a[idx[u]][1];
      |        ^~
events.cpp:101:27: warning: unused variable 'ut' [-Wunused-variable]
  101 |    int us = a[idx[u]][0], ut = a[idx[u]][1];
      |                           ^~
events.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d %d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d %d", &a[i][1], &a[i][0]); a[i][2] = i;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   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 186 ms 29484 KB Output is correct
3 Correct 195 ms 29488 KB Output is correct
4 Correct 221 ms 29532 KB Output is correct
5 Correct 200 ms 33060 KB Output is correct
6 Correct 213 ms 33552 KB Output is correct
7 Correct 216 ms 33752 KB Output is correct
8 Incorrect 220 ms 39800 KB Output isn't correct
9 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 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Incorrect 3 ms 520 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 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Incorrect 3 ms 520 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 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Incorrect 3 ms 520 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 190 ms 29552 KB Output is correct
2 Correct 201 ms 29488 KB Output is correct
3 Correct 211 ms 29648 KB Output is correct
4 Correct 220 ms 39692 KB Output is correct
5 Correct 217 ms 32840 KB Output is correct
6 Correct 262 ms 39400 KB Output is correct
7 Correct 256 ms 39504 KB Output is correct
8 Correct 237 ms 39588 KB Output is correct
9 Correct 182 ms 34364 KB Output is correct
10 Correct 234 ms 39052 KB Output is correct
11 Correct 229 ms 38844 KB Output is correct
12 Correct 242 ms 39020 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 186 ms 29484 KB Output is correct
3 Correct 195 ms 29488 KB Output is correct
4 Correct 221 ms 29532 KB Output is correct
5 Correct 200 ms 33060 KB Output is correct
6 Correct 213 ms 33552 KB Output is correct
7 Correct 216 ms 33752 KB Output is correct
8 Incorrect 220 ms 39800 KB Output isn't correct
9 Halted 0 ms 0 KB -