Submission #613175

#	Time	Username	Problem	Language	Result	Execution time	Memory
613175		M_W	Event Hopping (BOI22_events)	C++17	20 / 100	324 ms	36332 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; 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 (stderr)

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