oj.uz

Submission #860238

# Submission time Handle Problem Language Result Execution time Memory
860238 2023-10-12T09:34:39 Z aaron_dcoder Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 71688 KB 
#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;
	}
};


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;
		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)
		{
			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];
		ll numjmps=1;

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

		while (ei != -1 && events[ei].e0>events[si].e1) {
			ei = jmpto[ei];
			numjmps++;
		}

		
		if (ei==-1) {
			cout << "impossible\n";
		}
		else {
			cout << numjmps <<"\n";
		}
		
	}

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 1588 ms 71680 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Execution timed out 1591 ms 1116 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Execution timed out 1591 ms 1116 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Execution timed out 1591 ms 1116 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1527 ms 71688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 1588 ms 71680 KB Time limit exceeded
3 Halted 0 ms 0 KB -