Submission #612642

#	Time	Username	Problem	Language	Result	Execution time	Memory
612642		M_W	Event Hopping (BOI22_events)	C++17	20 / 100	265 ms	39776 KiB

events

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30