Submission #918743

#	Time	Username	Problem	Language	Result	Execution time	Memory
918743		dsyz	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	369 ms	53328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (200005)
ll N,Q, sum = 1;
ll parent[20][MAXN];
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N;
	pair<ll,ll> arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i].first>>arr[i].second;
	}
	set<pair<ll,ll> > s; //all ranges in the set do not intersect at any point in time so do not need to use multiset
	ll Rptr = 0;
	for(ll L = 0;L < N;L++){ //for each element L, the range where L can jump to with no extra cost (Rptr) is increasing monotonically
		while(Rptr < N){
			bool ok = 1;
			auto it = s.lower_bound({arr[Rptr].first,-1e18});
			if(!s.empty() && it != s.end()){
				if(it->first <= arr[Rptr].second) ok = 0;
			}
			if(!s.empty() && it != s.begin()){ //remember that all ranges in the set do not intersect so (it--) [element with greatest L value] would have the greatest R value
				it--;
				if(it->second >= arr[Rptr].first) ok = 0;
			}
			if(ok){
				s.insert(arr[Rptr]);
				Rptr++;
			}else{
				break;
			}
		}
		parent[0][L] = Rptr; //I can jump from L to Rptr with no cost ([L,Rptr - 1] can be in same lineup)
		s.erase(s.find(arr[L]));
	}
	for(ll k = 0;k < 20;k++){ //since I set out-of-range as N, then i must make sure that my imaginary N pos is a stopper (self loop because there is no more position to jump towards on the right anymore)
		parent[k][N] = N;
	}
	for(ll k = 1;k < 20;k++){
		for(ll i = 0;i < N;i++){
			parent[k][i] = parent[k-1][parent[k - 1][i]];
		}
	}
	cin>>Q;
	for(ll q = 0;q < Q;q++){
		ll a,b;
		cin>>a>>b;
		a--, b--;
		ll sum = 1; //number of lineups needed to jump from a to b
		//note that this 2k-decomp is different from "ancestor" (instead of the usual way of jumping d distance, we need to jump to pos b (or less if its lineup start before pos b) which is unknown distance away
		//we set parent[0][x] to be the nearest pos that cannot be in the same lineup as x (so the distance is all messed up already)
		//then because we do not know the exact distance to jump but we can rely on the index to know if we will overjump or not (since we are jumping on an array)
		for(ll k = 19;k >= 0;k--){
			if(parent[k][a] <= b){
				a = parent[k][a];
				sum += (1ll<<k);
			}
		}
		cout<<sum<<'\n';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50