oj.uz

Submission #613175

# Submission time Handle Problem Language Result Execution time Memory
613175 2022-07-30T03:47:50 Z M_W Event Hopping (BOI22_events) C++17
20 / 100
 324 ms 36332 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; i <= N; i++){
		ii res = query(1, 1, cnt, a[i][0], a[i][1]);
		if(res.first == INT_MAX) up[i][0] = i;
		else{
			up[i][0] = res.second;
			dist[i][0] = 1;
		}
		
		for(int j = 1; j <= 20; j++){
			up[i][j] = up[up[i][j - 1]][j - 1];
			dist[i][j] = dist[i][j - 1] + dist[up[i][j - 1]][j - 1];
		}
		ins(1, 1, cnt, i, a[i][0], a[i][1]);
	}
	for(int i = 1, u, v; i <= Q; i++){
		scanf("%d %d", &u, &v);
		int st = idx[u], ed = idx[v];
		
		int ans = 0;
		for(int j = 20; j >= 0; j--){
			if(up[ed][j] > st){
				ans += dist[ed][j];
				ed = up[ed][j];
			}	
		}
		if(ed > st){
			ans++;
			ed = up[ed][0];
		}
		
		if(idx[u] > idx[v] || ed > st) printf("impossible\n");
		else printf("%d\n", ans);
	}
}

Compilation message

events.cpp: In function 'int main()':
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:86:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   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 187 ms 29060 KB Output is correct
3 Correct 202 ms 29124 KB Output is correct
4 Correct 206 ms 28880 KB Output is correct
5 Correct 228 ms 29484 KB Output is correct
6 Correct 238 ms 29896 KB Output is correct
7 Correct 229 ms 30076 KB Output is correct
8 Correct 234 ms 36128 KB Output is correct
9 Correct 216 ms 36332 KB Output is correct
10 Correct 218 ms 29508 KB Output is correct
11 Incorrect 270 ms 33420 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Incorrect 3 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 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Incorrect 3 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 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Incorrect 3 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 223 ms 28900 KB Output is correct
2 Correct 235 ms 28900 KB Output is correct
3 Correct 233 ms 29016 KB Output is correct
4 Correct 228 ms 36232 KB Output is correct
5 Correct 222 ms 29360 KB Output is correct
6 Correct 324 ms 35796 KB Output is correct
7 Correct 277 ms 35820 KB Output is correct
8 Correct 285 ms 35952 KB Output is correct
9 Correct 184 ms 34364 KB Output is correct
10 Correct 237 ms 35496 KB Output is correct
11 Correct 295 ms 35328 KB Output is correct
12 Correct 214 ms 35428 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 187 ms 29060 KB Output is correct
3 Correct 202 ms 29124 KB Output is correct
4 Correct 206 ms 28880 KB Output is correct
5 Correct 228 ms 29484 KB Output is correct
6 Correct 238 ms 29896 KB Output is correct
7 Correct 229 ms 30076 KB Output is correct
8 Correct 234 ms 36128 KB Output is correct
9 Correct 216 ms 36332 KB Output is correct
10 Correct 218 ms 29508 KB Output is correct
11 Incorrect 270 ms 33420 KB Output isn't correct
12 Halted 0 ms 0 KB -