oj.uz

Submission #612606

# Submission time Handle Problem Language Result Execution time Memory
612606 2022-07-29T18:12:42 Z M_W Event Hopping (BOI22_events) C++17
0 / 100
 287 ms 32648 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 = 0;
			for(int j = 20; j >= 0; j--){
				if(up[start][j] > idx[u]){
					ans += dist[start][j];
					start = up[start][j];
				}
			}
			ans += dist[start][0];
			start = up[start][0];

			A[query_pos] = (start <= idx[u] && idx[u] <= idx[v]) ? ans + 1 : -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 1 ms 340 KB Output is correct
2 Correct 220 ms 32636 KB Output is correct
3 Correct 230 ms 32556 KB Output is correct
4 Incorrect 276 ms 32536 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 32648 KB Output is correct
2 Correct 217 ms 32564 KB Output is correct
3 Incorrect 287 ms 32392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 220 ms 32636 KB Output is correct
3 Correct 230 ms 32556 KB Output is correct
4 Incorrect 276 ms 32536 KB Output isn't correct
5 Halted 0 ms 0 KB -