Submission #860250

#	Time	Username	Problem	Language	Result	Execution time	Memory
860250		aaron_dcoder	Event Hopping (BOI22_events)	C++17	100 / 100	115 ms	86944 KiB

events

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 1e11;
template<class T>
struct sptable {
	array<vector<pair<T,ll>>,20> cache;

	sptable(vector<T> arr) {
		cache.fill(vector<pair<T,ll>>(arr.size()));

		for (ll i = 0; i < (ll)arr.size(); ++i)
		{
			cache[0][i]=make_pair(arr[i],i);
		}
		
		for (ll p = 1; p < 20; p++)
		{
			for (ll i = 0; i <= ((ll)arr.size()) - (1<<p); ++i)
			{dbg(p << "f" << i);

				cache[p][i] = min(cache[p-1][i], cache[p-1][i+(1<<(p-1))]);
				dbgv(cache[p][i].e0.e0);
				dbg("h");
			}
		}
		dbg("yay");
	}

	pair<T,ll> rmq(ll b, ll e) {
		ll s = e-b+1;
		ll p = 63-__builtin_clzll(s);
		return min(cache[p][b],cache[p][e-(1<<p)+1]);
	}
};

struct ev {
	ll first;
	ll second;
	ll idx;

	bool operator<(const ev& b) const {
		return e0 < b.e0;
	}
};

ll jumptill(ll ei, ll si, ll maxpow, const vector<ll>* powjmp, const vector<ev>& events) {
	dbgv(maxpow);
	if (maxpow<=2) {
		ll numjmps=1;
		while (ei != -1 && events[ei].e0>events[si].e1) {
			ei = powjmp[0][ei];
			numjmps++;
		}
		if (ei==-1) return -INFTY;
		else return numjmps;
	}

	ll nei = powjmp[maxpow][ei];
	if (nei != -1 && events[nei].e0>events[si].e1) {
		return (1<<maxpow) + jumptill(nei,si,maxpow-1,powjmp, events);
	}
	else {
		return jumptill(ei,si,maxpow-1,powjmp, events);
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ll N,Q;
	cin >> N >> Q;
// {s,e}
	vector<ev> events(N);
	vector<ll> events_indice(N+1);

	for (int i = 0; i < N; ++i)
	{
		cin >> events[i].e0 >> events[i].e1;
		events[i].idx = i+1;
	}

	auto cmpe = [](const ev& a, const ev& b) {
		return a.e1 < b.e1;
	};

	sort(events.begin(),events.end(), cmpe);

	for (ll i = 0; i < N; ++i)
	{
		events_indice[events[i].idx]=i;
	}


	sptable<ev> jmpfnd(events);

	vector<ll> jmpto(N);

	auto cmpe2 = [](ll a, const ev& b) {
		return a < b.e1;
	};
	auto cmpe3= [](const ev& a, ll b) {
		return a.e1 < b;
	};

	for (ll i = 0; i < N; ++i)
	{
		ll lb = lower_bound(events.cbegin(),events.cend(), events[i].e0, cmpe3) - events.cbegin();
		ll ub = upper_bound(events.cbegin(),events.cend(), events[i].e1, cmpe2) - events.cbegin() - 1;
		dbgv(lb << ub);
		if (lb==ub) {
			assert(lb==i);
			jmpto[i] = -1;
		}
		else {
			jmpto[i] = jmpfnd.rmq(lb, ub).e1;
			if (jmpto[i]==i) {
				jmpto[i] = -1;
			}
		}
		dbgv(jmpto[i]);
	}


	array<vector<ll>,20> powjmp;
	powjmp[0] = jmpto;

	for (ll p = 1; p < 20; p++)
	{
		powjmp[p].assign(N,-2);
		for (ll i = 0; i < N; ++i)
		{
			if (powjmp[p-1][i]==-1) powjmp[p][i] = -1;
			else powjmp[p][i] = powjmp[p-1][powjmp[p-1][i]];
		}
	}

	for (ll qno=0; qno < Q; qno++)
	{
		ll si,ei;
		cin >> si >> ei;
		si = events_indice[si];
		ei = events_indice[ei];
		

		if (si==ei) {
			cout << "0\n";
			continue;
		}
		if (events[si].e1 > events[ei].e1) {
			cout << "impossible\n";
			continue;
		}dbgv(ei);

		ll numjmps=jumptill(ei,si,19,powjmp.data(),events);
		
		if (numjmps<=0) {
			cout << "impossible\n";
		}
		else {
			cout << numjmps <<"\n";
		}
		
	}

}

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