結果
| 問題 |
No.913 木の燃やし方
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:36 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 122 ms / 3,000 ms |
| コード長 | 9,297 bytes |
| コンパイル時間 | 837 ms |
| コンパイル使用メモリ | 81,024 KB |
| 実行使用メモリ | 15,584 KB |
| 最終ジャッジ日時 | 2025-05-14 13:03:55 |
| 合計ジャッジ時間 | 7,893 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// Use long long for values that can exceed 32-bit integer limits
typedef long long ll;
// Use __int128 for intermediate calculations in CHT check to prevent overflow
// Products of differences can exceed 64 bits when N is large and |A_i| is large.
typedef __int128 int128;
// A large value to represent infinity, ensuring it's larger than any possible sadness value.
// Max sadness could be around N^2 + N * max(A_i) ~ 4e10 + 2e5 * 1e9 = 4e10 + 2e14.
// Min sadness could be negative. Use a large positive value for initial minimums.
const ll INF = 4e18;
// Structure to represent points for Convex Hull Trick
// x coordinate stores 'l', y coordinate stores 'h(l) = l^2 - P_l'
struct Point {
ll x, y;
};
// Function to check if point P2 is redundant for the lower convex hull given P1 and P3.
// Returns true if P2 lies on or above the line segment P1P3, meaning P2 should be removed.
// Uses cross product with 128-bit integers to avoid overflow and floating point precision issues.
// Assumes p1.x < p2.x < p3.x.
bool check_redundant(Point p1, Point p2, Point p3) {
// Calculate (p2.y - p1.y) * (p3.x - p2.x) and (p3.y - p2.y) * (p2.x - p1.x)
int128 val1 = (int128)(p2.y - p1.y) * (p3.x - p2.x);
int128 val2 = (int128)(p3.y - p2.y) * (p2.x - p1.x);
// If slope(P1, P2) >= slope(P2, P3), P2 is redundant for lower hull.
return val1 >= val2;
}
// Global vector to store points of the lower convex hull for the current subproblem
// Reused across recursive calls to potentially save memory allocation time.
vector<Point> cht_hull;
// Builds the lower convex hull for points[l_idx_start...l_idx_end] from the global set of points.
// The global points `global_h_points` contains (l, h(l)) for l=0..N-1.
void build_cht(const vector<Point>& global_h_points, int l_idx_start, int l_idx_end) {
cht_hull.clear(); // Clear hull from previous usage
// Ensure the range is valid
if (l_idx_start > l_idx_end) return;
// Iterate through the specified range of 'l' indices
for (int i = l_idx_start; i <= l_idx_end; ++i) {
// Get the point corresponding to index l=i
Point p = global_h_points[i];
// Maintain the convex hull property: remove points from the back of the hull
// if they become redundant with the new point p.
while (cht_hull.size() >= 2 && check_redundant(cht_hull[cht_hull.size() - 2], cht_hull.back(), p)) {
cht_hull.pop_back();
}
// Add the new point to the hull
cht_hull.push_back(p);
}
}
int N; // Number of trees
vector<ll> A; // Tree values A[1...N]
vector<ll> P; // Prefix sums P[k] = sum_{j=1..k} A_j. P[0] = 0.
vector<Point> h_points; // Globally stored points (l, h(l)) = (l, l^2 - P_l) for l=0..N-1
vector<ll> min_sadness; // Stores the result M_i (minimum sadness for tree i) for each i=1..N
// Recursive function implementing the Divide and Conquer Optimization strategy.
// Computes min_sadness[i] for all i in the range [i_s, i_e].
// The search space for the optimal pair (l, r) is restricted by the ranges [l_s, l_e] and [r_s, r_e].
void solve(int i_s, int i_e, int l_s, int l_e, int r_s, int r_e) {
// Base case: if the range of indices 'i' is empty, return.
if (i_s > i_e) {
return;
}
// Find the middle index i_m for the current range [i_s, i_e].
int i_m = i_s + (i_e - i_s) / 2;
// Determine the effective ranges for l and r specific to computing M_{i_m}.
// These ranges must satisfy l < i_m and r >= i_m, and also respect the current bounds [l_s, l_e] and [r_s, r_e].
int current_l_s = l_s;
int current_l_e = min(l_e, i_m - 1); // l must be <= i_m - 1
int current_r_s = max(r_s, i_m); // r must be >= i_m
int current_r_e = r_e;
ll current_min_sadness_for_im = INF; // Initialize minimum sadness for i_m to infinity.
int best_l = -1, best_r = -1; // Store the (l, r) pair that achieves the minimum sadness for i_m.
// Only proceed with CHT calculation if valid ranges for both l and r exist.
if (current_l_s <= current_l_e && current_r_s <= current_r_e) {
// Build the Convex Hull Trick structure using points h(l) for l in the effective range [current_l_s, current_l_e].
build_cht(h_points, current_l_s, current_l_e);
// Pointer used for optimizing CHT queries since query slopes are monotonic.
int CHT_ptr = 0;
// Iterate through possible values of r in its effective range.
for (int r = current_r_s; r <= current_r_e; ++r) {
// If the CHT hull is empty, there are no valid 'l' points for this range. Stop iterating r.
if (cht_hull.empty()) break;
// The query slope for CHT is -2r. We want to minimize h(l) - 2rl.
ll slope = -2LL * r;
// Optimize CHT query using the sliding pointer approach.
// Since slopes are decreasing as r increases, the optimal point index on the hull is non-decreasing.
// Move the pointer `CHT_ptr` right as long as the next point on the hull gives a smaller or equal value.
while (CHT_ptr < cht_hull.size() - 1) {
ll val1 = cht_hull[CHT_ptr].y + slope * cht_hull[CHT_ptr].x;
ll val2 = cht_hull[CHT_ptr+1].y + slope * cht_hull[CHT_ptr+1].x;
if (val1 >= val2) { // If next point is better or same, move pointer
CHT_ptr++;
} else {
break; // Current point at CHT_ptr is optimal for this slope
}
}
// Calculate the minimum value of h(l) - 2rl using the optimal point found by CHT pointer.
ll query_val = cht_hull[CHT_ptr].y + slope * cht_hull[CHT_ptr].x;
// Calculate the total sadness H(l,r) = (h(l) - 2rl) + r^2 + P_r.
ll total_sadness = query_val + (ll)r * r + P[r];
// Retrieve the optimal 'l' value (stored in the x coordinate of the CHT point).
int current_l = cht_hull[CHT_ptr].x;
// Update the minimum sadness found so far for i_m if the current interval [l+1, r] gives a smaller sadness.
if (total_sadness < current_min_sadness_for_im) {
current_min_sadness_for_im = total_sadness;
best_l = current_l; // Store the l that achieved this minimum
best_r = r; // Store the r that achieved this minimum
}
}
}
// Store the computed minimum sadness for index i_m in the result array.
min_sadness[i_m] = current_min_sadness_for_im;
// Perform recursive calls for the left subproblem (indices i < i_m) and the right subproblem (indices i > i_m).
// Pass potentially tighter bounds for l and r based on the optimal pair (best_l, best_r) found for i_m.
// This relies on the monotonicity property: l_i* and r_i* are non-decreasing functions of i.
if (best_l == -1) {
// If no valid interval was found for i_m (e.g., initial bounds were too restrictive, or sadness remains INF),
// it indicates an issue or edge case. To be safe, use the originally passed bounds for recursive calls.
// This ensures correctness but might skip potential optimization if bounds could actually be tightened.
solve(i_s, i_m - 1, l_s, l_e, r_s, r_e);
solve(i_m + 1, i_e, l_s, l_e, r_s, r_e);
} else {
// Apply monotonicity constraints to restrict search space in recursive calls:
// For the left subproblem (i < i_m): optimal l <= best_l, optimal r <= best_r.
// Pass updated upper bounds for l and r.
solve(i_s, i_m - 1, l_s, min(l_e, best_l), r_s, min(r_e, best_r));
// For the right subproblem (i > i_m): optimal l >= best_l, optimal r >= best_r.
// Pass updated lower bounds for l and r.
solve(i_m + 1, i_e, max(l_s, best_l), l_e, max(r_s, best_r), r_e);
}
}
int main() {
// Use fast I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read input N, the number of trees
cin >> N;
// Resize vectors to accommodate N trees (using 1-based indexing for A and P for convenience)
A.resize(N + 1);
P.resize(N + 1);
P[0] = 0; // Initialize prefix sum base case
// Read tree values and compute prefix sums
for (int i = 1; i <= N; ++i) {
cin >> A[i];
P[i] = P[i - 1] + A[i];
}
// Precompute points (l, h(l)) = (l, l^2 - P_l) for CHT, for l from 0 to N-1.
// Note: Index l corresponds to the start of the interval L = l+1.
h_points.resize(N);
for (int l = 0; l < N; ++l) {
h_points[l] = { (ll)l, (ll)l * l - P[l] };
}
// Initialize the result vector to store minimum sadness for each tree i (1 to N).
min_sadness.resize(N + 1);
// Start the divide and conquer process for all indices i from 1 to N.
// The initial search ranges cover all possible l (0 to N-1) and r (1 to N).
solve(1, N, 0, N - 1, 1, N);
// Output the computed minimum sadness for each tree i.
for (int i = 1; i <= N; ++i) {
cout << min_sadness[i] << "\n";
}
return 0;
}