結果
| 問題 | No.2242 Cities and Teleporters |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:58:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,574 ms / 3,000 ms |
| コード長 | 10,915 bytes |
| コンパイル時間 | 1,382 ms |
| コンパイル使用メモリ | 124,416 KB |
| 実行使用メモリ | 48,760 KB |
| 最終ジャッジ日時 | 2025-05-14 13:00:08 |
| 合計ジャッジ時間 | 24,299 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 26 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath> // Include for ceil, log2
#include <stdexcept> // For runtime_error
using namespace std;
// Use long long for altitude/threshold as they can be up to 10^9
using ll = long long;
// Structure to store city data along with original index
// Although original ID is not directly used in the algorithm, keeping it might be useful for debugging.
struct City {
int id; // Original 1-based ID
ll h;
ll t;
};
// Comparator for sorting cities by altitude H
bool compareCities(const City& a, const City& b) {
return a.h < b.h;
}
// Global constants and data structures for binary lifting approach
const int LOGN_MAX = 19; // Max log2(2e5) is approx 17.6. Use 19 to be safe.
map<ll, int> value_to_idx; // Map T values to dense indices 0..V-1
vector<ll> idx_to_value; // Map dense indices back to T values
vector<vector<int>> jump; // jump[p][idx] stores the index of f^(2^p)(value at idx)
vector<ll> H_sorted; // Store sorted H values for efficient lookup
vector<ll> PMT; // Prefix maximum T values for cities sorted by altitude
int N_global; // Store N globally for convenience in helper functions
/**
* @brief Finds the count of cities with altitude <= val. This corresponds to the 1-based index `k`
* in the list of cities sorted by altitude such that the k-th city has the maximum altitude <= val.
* @param val The altitude threshold.
* @return The count of cities with altitude <= val. Returns 0 if no city satisfies the condition.
*/
int find_idx(ll val) {
// `upper_bound` finds the first element in H_sorted strictly greater than val.
auto it = upper_bound(H_sorted.begin(), H_sorted.end(), val);
// The distance from the beginning to this iterator is the count of elements <= val.
return distance(H_sorted.begin(), it);
}
/**
* @brief Calculates T_max(val) = max { T_j | H_j <= val }.
* This is the maximum teleporter threshold among all cities j whose altitude H_j is at most val.
* @param val The altitude threshold.
* @return The maximum T value found. Returns -1 if no city has altitude <= val.
*/
ll calculate_T_max(ll val) {
// Find the count k' of cities with H <= val.
int k_prime = find_idx(val);
if (k_prime == 0) {
// No city satisfies H_j <= val. Conceptually, T_max is -infinity. We represent this with -1.
return -1;
}
// PMT[k] stores the max T value among the first k cities sorted by altitude.
// Since k_prime is the count, it's the correct 1-based index for PMT.
return PMT[k_prime];
}
/**
* @brief Applies the state transition function f(M) = max(M, T_max(M)).
* This function computes the maximum teleporter threshold reachable in the next step,
* given the current maximum threshold M.
* @param M_val The current maximum threshold M.
* @return The maximum threshold after one step transition.
*/
ll apply_f(ll M_val) {
ll t_max = calculate_T_max(M_val);
if (t_max == -1) {
// If T_max is -infinity (no city reachable), the threshold doesn't increase.
return M_val;
}
// The new threshold is the maximum of the current one and the T_max achievable.
return max(M_val, t_max);
}
/**
* @brief Computes f^(k)(M_val), i.e., applying the function f k times starting from M_val.
* Uses binary lifting (sparse table `jump`) for efficient computation.
* @param M_val The initial maximum threshold.
* @param k The number of steps (applications of f).
* @return The maximum threshold after k steps.
*/
ll compute_f_k(ll M_val, int k) {
// Basic validation: k must be non-negative.
if (k < 0) throw runtime_error("k must be non-negative in compute_f_k");
// If k=0, no steps are taken, return the initial value.
if (k == 0) return M_val;
// Determine the maximum power of 2 needed for binary lifting based on N
int LOGN = N_global > 1 ? ceil(log2(N_global)) + 1 : 1; // Use ceil + 1 for safety
LOGN = min(LOGN, LOGN_MAX); // Cap LOGN to avoid excessive memory/computation
ll current_M = M_val;
int current_idx = -1; // Index in the value map corresponding to current_M
// Check if the initial M_val is one of the T values we track.
auto it = value_to_idx.find(current_M);
if (it == value_to_idx.end()) {
// M_val is not in the map. This typically happens only if M_val = T_A and T_A is not in {T_1 .. T_N}.
// Compute one step manually to potentially transition to a value within the map.
current_M = apply_f(M_val);
k--; // One step accounted for.
if (k == 0) return current_M; // If only 1 step was needed.
// Check if the new M is now in the map.
it = value_to_idx.find(current_M);
if (it == value_to_idx.end()) {
// If it's still not in the map, this implies f(M_val) = M_val, meaning it stabilized immediately.
// Our analysis shows f(T_A) = max(T_A, T_k). If result is T_A, it stabilized. If T_k, it's in map.
// So this case means stabilization.
return M_val; // Return the value it stabilized at (which is the original M_val).
}
// If it is in map now, record its index.
current_idx = it->second;
} else {
// Initial M_val is in map. Record its index.
current_idx = it->second;
}
// Proceed with binary lifting for the remaining k steps using the jump table.
// Iterate through powers of 2 from largest down to smallest is standard, but 0 up works too.
for (int p = 0; p < LOGN; ++p) {
// If the p-th bit of k is set, it means we need to take a jump of size 2^p.
if ((k >> p) & 1) {
current_idx = jump[p][current_idx];
}
}
// After applying all necessary jumps, return the value corresponding to the final index.
return idx_to_value[current_idx];
}
int main() {
// Enable Fast IO
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// Read number of cities
cin >> N_global;
int N = N_global;
vector<City> cities(N);
vector<ll> T_vals_orig(N); // Store original T values to build map later
// Read altitudes H_i
for (int i = 0; i < N; ++i) {
cities[i].id = i + 1; // Store 1-based ID
cin >> cities[i].h;
}
// Read teleporter thresholds T_i
for (int i = 0; i < N; ++i) {
cin >> cities[i].t;
T_vals_orig[i] = cities[i].t;
}
// Sort cities by altitude H to prepare for T_max calculation
vector<City> sorted_cities = cities;
sort(sorted_cities.begin(), sorted_cities.end(), compareCities);
// Populate H_sorted and PMT (prefix maximum T) arrays
H_sorted.resize(N);
PMT.resize(N + 1); // Use 1-based indexing for PMT for convenience
PMT[0] = -1LL; // Base case: max T for empty prefix is -infinity
for (int i = 0; i < N; ++i) {
H_sorted[i] = sorted_cities[i].h;
// PMT[i+1] stores max T among first i+1 cities (indices 0 to i) sorted by H
PMT[i + 1] = max(PMT[i], sorted_cities[i].t);
}
// Prepare value map (value_to_idx, idx_to_value) for T values
// Collect distinct T values
vector<ll> distinct_T = T_vals_orig;
sort(distinct_T.begin(), distinct_T.end());
distinct_T.erase(unique(distinct_T.begin(), distinct_T.end()), distinct_T.end());
// Build the map and inverse map
int distinct_count = 0;
for (ll t_val : distinct_T) {
value_to_idx[t_val] = distinct_count++;
idx_to_value.push_back(t_val);
}
int V = distinct_count; // Number of distinct T values
int LOGN = N > 1 ? ceil(log2(N)) + 1 : 1; // Calculate required LOGN based on N
LOGN = min(LOGN, LOGN_MAX); // Cap LOGN to defined maximum
// Initialize jump table
jump.resize(LOGN, vector<int>(V));
// Precompute jump table Base case: p=0 (jump of size 2^0 = 1)
for (int i = 0; i < V; ++i) {
ll current_val = idx_to_value[i];
ll next_val = apply_f(current_val); // Apply f once
auto it = value_to_idx.find(next_val);
if (it != value_to_idx.end()) {
// Store the index corresponding to the next value
jump[0][i] = it->second;
} else {
// According to analysis, f(T_i) should always yield a value that is also a T_j (possibly T_i itself).
// If next_val is not found in the map, it indicates an error in reasoning or implementation.
throw runtime_error("f(T_i) result not found in map during precomputation");
}
}
// Compute jump table for p > 0 using dynamic programming approach
// jump[p][i] = jump[p-1][ jump[p-1][i] ] essentially jumps 2^(p-1) steps twice.
for (int p = 1; p < LOGN; ++p) {
for (int i = 0; i < V; ++i) {
jump[p][i] = jump[p - 1][jump[p - 1][i]];
}
}
// Read number of queries
int Q;
cin >> Q;
// Process each query
while (Q--) {
int A_idx, B_idx; // Read 1-based city indices
cin >> A_idx >> B_idx;
int A = A_idx - 1; // Convert to 0-based index
int B = B_idx - 1;
ll T_A = cities[A].t; // Teleporter threshold of starting city A
ll H_B = cities[B].h; // Altitude of destination city B
// Check base case: Can B be reached in 1 step from A?
// Condition: H_B <= T_A (altitude of B is within A's teleporter threshold)
if (H_B <= T_A) {
cout << 1 << "\n";
continue; // Process next query
}
// Binary search for the minimum number of steps k >= 1.
// Search space for k is [1, N]. Max steps needed is N-1, but checking up to N is safe.
int low = 1, high = N, ans = -1; // Initialize answer to -1 (unreachable)
while(low <= high) {
int mid_k = low + (high - low) / 2; // Candidate minimum steps
// Check if B is reachable within mid_k steps.
// The condition is H_B <= M_{mid_k - 1}, where M_{k} = f^k(T_A).
// Compute M_{mid_k - 1} using binary lifting function.
ll M_km1 = compute_f_k(T_A, mid_k - 1);
if (H_B <= M_km1) {
// If H_B is within the threshold after mid_k - 1 steps,
// it means B is reachable in mid_k steps (or possibly earlier).
ans = mid_k; // mid_k is a possible answer.
high = mid_k - 1; // Try to find a smaller k.
} else {
// If H_B is greater than the threshold, mid_k steps are not enough.
low = mid_k + 1; // Need more steps, minimum k must be > mid_k.
}
}
// Output the minimum steps found, or -1 if unreachable.
cout << ans << "\n";
}
return 0;
}