oj.uz

Submission #612620

# Submission time Handle Problem Language Result Execution time Memory
612620 2022-07-29T18:22:35 Z M_W Event Hopping (BOI22_events) C++17
20 / 100
 287 ms 36828 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 * 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({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 193 ms 29548 KB Output is correct
3 Correct 208 ms 29472 KB Output is correct
4 Correct 214 ms 29472 KB Output is correct
5 Correct 210 ms 30108 KB Output is correct
6 Correct 250 ms 30524 KB Output is correct
7 Correct 201 ms 30604 KB Output is correct
8 Incorrect 253 ms 36732 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 1 ms 340 KB Output is correct
3 Correct 2 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 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 1 ms 340 KB Output is correct
3 Correct 2 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 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 1 ms 340 KB Output is correct
3 Correct 2 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 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 230 ms 29560 KB Output is correct
2 Correct 216 ms 29484 KB Output is correct
3 Correct 241 ms 29500 KB Output is correct
4 Correct 222 ms 36828 KB Output is correct
5 Correct 230 ms 29912 KB Output is correct
6 Correct 264 ms 36444 KB Output is correct
7 Correct 287 ms 36436 KB Output is correct
8 Correct 258 ms 36584 KB Output is correct
9 Correct 180 ms 32584 KB Output is correct
10 Correct 241 ms 36036 KB Output is correct
11 Correct 257 ms 35828 KB Output is correct
12 Correct 234 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 193 ms 29548 KB Output is correct
3 Correct 208 ms 29472 KB Output is correct
4 Correct 214 ms 29472 KB Output is correct
5 Correct 210 ms 30108 KB Output is correct
6 Correct 250 ms 30524 KB Output is correct
7 Correct 201 ms 30604 KB Output is correct
8 Incorrect 253 ms 36732 KB Output isn't correct
9 Halted 0 ms 0 KB -