Submission #580724

#	Time	Username	Problem	Language	Result	Execution time	Memory
580724		penguinhacker	Event Hopping (BOI22_events)	C++17	100 / 100	191 ms	25276 KiB

events

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, q, lg[2*mxN+1], st[2*mxN][18], lift[mxN][17];
ar<int, 2> events[mxN];
vector<int> d;

int cmb(int a, int b) {
	if (a==-1||b==-1)
		return a==-1?b:a;
	return events[a][0]<events[b][0]?a:b;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i=0; i<n; ++i) {
		cin >> events[i][0] >> events[i][1];
		d.push_back(events[i][0]);
		d.push_back(events[i][1]);
	}
	sort(d.begin(), d.end());
	d.resize(unique(d.begin(), d.end())-d.begin());
	memset(st, -1, sizeof(st));
	for (int i=0; i<n; ++i) {
		events[i][0]=lower_bound(d.begin(), d.end(), events[i][0])-d.begin();
		events[i][1]=lower_bound(d.begin(), d.end(), events[i][1])-d.begin();
		st[events[i][1]][0]=cmb(st[events[i][1]][0], i);
	}
	for (int i=2; i<=d.size(); ++i)
		lg[i]=lg[i/2]+1;
	for (int j=1; (1<<j)<=d.size(); ++j)
		for (int i=0; i+(1<<j)-1<d.size(); ++i)
			st[i][j]=cmb(st[i][j-1], st[i+(1<<j-1)][j-1]);
	for (int i=0; i<n; ++i) {
		int k=lg[events[i][1]-events[i][0]+1];
		lift[i][0]=cmb(st[events[i][0]][k], st[events[i][1]-(1<<k)+1][k]);
		assert(lift[i][0]!=-1);
	}
	for (int j=1; j<17; ++j)
		for (int i=0; i<n; ++i)
			lift[i][j]=lift[lift[i][j-1]][j-1];
	while(q--) {
		int a, b;
		cin >> a >> b, --a, --b;
		if (events[a][1]>events[b][1]) {
			cout << "impossible\n";
			continue;
		}
		if (events[b][0]<=events[a][1]&&events[a][1]<=events[b][1]) {
			cout << (a!=b) << "\n";
			continue;
		}
		int ans=0;
		for (int i=16; ~i; --i)
			if (events[lift[b][i]][0]>events[a][1])
				b=lift[b][i], ans+=1<<i;
		if (events[lift[b][0]][0]>events[a][1]) {
			cout << "impossible\n";
			continue;
		}
		cout << ans+2 << "\n";
	}
	return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i=2; i<=d.size(); ++i)
      |                ~^~~~~~~~~~
events.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int j=1; (1<<j)<=d.size(); ++j)
      |                ~~~~~~^~~~~~~~~~
events.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int i=0; i+(1<<j)-1<d.size(); ++i)
      |                 ~~~~~~~~~~^~~~~~~~~
events.cpp:39:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |    st[i][j]=cmb(st[i][j-1], st[i+(1<<j-1)][j-1]);
      |                                      ~^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30