제출 #1251238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251238		ksun48	Obstacles for a Llama (IOI25_obstacles)	C++20	100 / 100	261 ms	82700 KiB

obstacles

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

namespace {
	vector<pair<int,int>> interval;
	vector<int> l_par, r_par;
	vector<vector<pair<int,int> > > l_jump_max, r_jump_min;
	int J;
	void my_initialize(vector<int> T, vector<int> H){
		T.push_back(0);
		T.push_back(int(1e9) + 1);
		for(int& x : T) x = 2*x-1 - int(1e9);
		for(int& x : H) x = 2*x - int(1e9);
		vector<pair<int,int> > T_maxs;
		vector<pair<int,int> > T_mins;
		for(int i = 0; i < (int)T.size(); i++){
			if(i == 0 || T[i] > T_maxs.back().first){
				T_maxs.push_back({T[i], i});
			}
			if(i == 0 || T[i] < -T_mins.back().first){
				T_mins.push_back({-T[i], i});
			}
		}
		int N = (int)H.size();
		vector<tuple<int,int,int>> locs;
		for(int i = 0; i < N; i++){
			if(T[0] > H[i]){
				// good
				int v = lower_bound(T_mins.begin(), T_mins.end(), pair<int,int>{-H[i], 0})->second;
				locs.push_back({v, 0, i});
			} else {
				// bad
				int v = lower_bound(T_maxs.begin(), T_maxs.end(), pair<int,int>{H[i], 0})->second;
				locs.push_back({v, 1, i});
			}
		}
		l_par.resize(N, -1);
		r_par.resize(N, -1);
		interval.resize(N, {-1, -1});
		set<pair<int,int> > active;
		active.insert({-1, 1});
		active.insert({N, 1});
		sort(locs.rbegin(), locs.rend());
		for(auto [h, ctype, i] : locs){
			if(ctype == 1){
				active.insert({i, 1});
				l_par[i] = r_par[i] = i;
			} else {
				auto [it, _] = active.insert({i, 0});
				auto [pi, pt] = *prev(it);
				auto [ni, nt] = *next(it);
				interval[i] = {pi, ni};
				if(pt && nt){
					l_par[i] = r_par[i] = i;
				} else if(pt){
					l_par[i] = r_par[i] = ni;
				} else if(nt){
					l_par[i] = r_par[i] = pi;
				} else {
					l_par[i] = pi;
					r_par[i] = ni;
				}
			}
		}
		while((1 << J) < N) J += 1;
		l_jump_max.assign(J, vector<pair<int,int>>(N));
		r_jump_min.assign(J, vector<pair<int,int>>(N));
		for(int i = 0; i < N; i++){
			l_jump_max[0][i] = {l_par[i], l_par[i]};
			r_jump_min[0][i] = {r_par[i], r_par[i]};
		}
		for(int j = 1; j < J; j++){
			for(int i = 0; i < N; i++){
				l_jump_max[j][i] = {l_jump_max[j-1][l_jump_max[j-1][i].first].first, 
					max(l_jump_max[j-1][i].second, l_jump_max[j-1][l_jump_max[j-1][i].first].second)};
				r_jump_min[j][i] = {r_jump_min[j-1][r_jump_min[j-1][i].first].first, 
					min(r_jump_min[j-1][i].second, r_jump_min[j-1][r_jump_min[j-1][i].first].second)};
			}
		}
	}

	bool my_can_reach(int L, int R, int S, int D){
		if(S > D) swap(S, D);
		int x = S;
		for(int j = J-1; j >= 0; j--){
			if(r_jump_min[j][x].second >= L){
				x = r_jump_min[j][x].first;
			}
		}
		if(interval[x].second < D) return false;
		x = D;
		for(int j = J-1; j >= 0; j--){
			if(l_jump_max[j][x].second <= R){
				x = l_jump_max[j][x].first;
			}
		}
		if(interval[x].first > S) return false;
		return true;
	}
}
void initialize(vector<int> T, vector<int> H){
	my_initialize(T, H);
}

bool can_reach(int L, int R, int S, int D){
	return my_can_reach(L, R, S, D);
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 21 / 21
• Subtask 5: 25 / 25
• Subtask 6: 17 / 17