oj.uz

Submission #860241

# Submission time Handle Problem Language Result Execution time Memory
860241 2023-10-12T09:38:18 Z aaron_dcoder Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 73912 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;
			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)
		{
			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 0 ms 348 KB Output is correct
2 Execution timed out 1585 ms 71528 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.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 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1112 KB Output is correct
9 Correct 1 ms 980 KB Output is correct

Subtask #3
15.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 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1112 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 302 ms 5240 KB Output is correct
20 Correct 885 ms 5856 KB Output is correct
21 Correct 178 ms 5808 KB Output is correct
22 Correct 20 ms 5820 KB Output is correct
23 Correct 20 ms 5564 KB Output is correct
24 Correct 20 ms 5576 KB Output is correct
25 Correct 33 ms 5184 KB Output is correct

Subtask #4
15.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 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1112 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 976 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 75 ms 73912 KB Output is correct
20 Correct 56 ms 72788 KB Output is correct
21 Correct 61 ms 73556 KB Output is correct
22 Correct 57 ms 73552 KB Output is correct
23 Correct 52 ms 73552 KB Output is correct
24 Correct 56 ms 73636 KB Output is correct
25 Correct 49 ms 72884 KB Output is correct

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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