結果
| 問題 |
No.2036 Max Middle
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:16:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,696 bytes |
| コンパイル時間 | 1,005 ms |
| コンパイル使用メモリ | 91,008 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:17:50 |
| 合計ジャッジ時間 | 5,393 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 4 TLE * 1 -- * 12 |
ソースコード
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
// Use long long for array values because the operation can decrease values potentially below the standard int range.
typedef long long ll;
// Global vector A to store the sequence, and N for its size.
vector<ll> A;
int N;
// A set to keep track of the indices k where A[k] is currently a peak.
// Using a set allows efficient checking of existence, insertion, and deletion (O(log N)).
set<int> peak_indices;
// A queue to manage the indices of peaks that need to be processed.
// Using a queue implements a breadth-first like processing order of peaks.
queue<int> worklist;
// Function to check if the element A[k] is a peak.
// According to the problem, A[k] is a peak if k is between 1 and N-2 (inclusive, using 0-based indexing for A)
// and satisfies the condition A[k-1] < A[k] and A[k] > A[k+1].
// Note: The problem statement uses 1-based indexing and defines the operation for index `i` where 1 <= i <= N-2.
// This corresponds to checking the triplet (A_i, A_{i+1}, A_{i+2}). In 0-based indexing, this triplet is (A[i-1], A[i], A[i+1]).
// The peak condition is A[i-1] < A[i] and A[i] > A[i+1].
// The element modified is A[i]. Let's denote the index `i` (from problem statement) as `k` in our code.
// So `k` represents the index of the element being modified/checked if it's a peak. Valid range for k is [1, N-2].
bool is_peak(int k) {
// Check if index k is within the valid range for a peak [1, N-2].
if (k < 1 || k > N - 2) {
return false;
}
// Check the peak condition: the element A[k] must be strictly greater than its left neighbor A[k-1]
// and strictly greater than its right neighbor A[k+1].
return A[k-1] < A[k] && A[k] > A[k+1];
}
// Function to update the status of a potential peak at index k.
// If k becomes a peak and wasn't tracked, add it to the set and worklist.
// If k ceases to be a peak and was tracked, remove it from the set.
void update_peak_status(int k) {
// Check if index k is within the valid range [1, N-2]. Indices outside this range cannot be peaks.
if (k < 1 || k > N - 2) {
return;
}
// Determine if A[k] is currently a peak based on current values of A.
bool current_is_peak = is_peak(k);
// Check if index k is currently present in our set of peak indices.
bool is_in_set = peak_indices.count(k);
// Case 1: A[k] is currently a peak, but k is not in our set.
// This means k has just become a peak (or was missed initially).
if (current_is_peak && !is_in_set) {
peak_indices.insert(k); // Add k to the set of peak indices.
worklist.push(k); // Add k to the worklist queue to be processed later.
}
// Case 2: A[k] is not currently a peak, but k is in our set.
// This means k used to be a peak but isn't anymore due to changes in neighbors.
else if (!current_is_peak && is_in_set) {
peak_indices.erase(k); // Remove k from the set of peak indices.
// Note: k might still be present in the worklist queue. If it gets popped later,
// the check `if (peak_indices.count(k) == 0)` will correctly skip it.
}
// Other cases:
// - If current_is_peak is true and is_in_set is true, k is already a known peak. No action needed.
// - If current_is_peak is false and is_in_set is false, k is not a peak and not tracked. No action needed.
}
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read the size of the sequence N.
cin >> N;
// Resize the vector A to hold N elements.
A.resize(N);
// Read the N integer elements into vector A.
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
// Initialize the process by finding all initial peaks.
// Iterate through all possible indices k that can be a peak (1 to N-2).
for (int k = 1; k <= N - 2; ++k) {
if (is_peak(k)) { // If A[k] satisfies the peak condition
peak_indices.insert(k); // Add its index k to the set of peaks.
worklist.push(k); // Add its index k to the initial worklist queue.
}
}
// Variable to keep track of the total number of operations performed.
ll total_ops = 0;
// Main loop: Process peaks from the worklist as long as it's not empty.
while (!worklist.empty()) {
int k = worklist.front(); // Get the index of the peak element A[k] from the front of the queue.
worklist.pop(); // Remove this index from the queue.
// Check if the index k is still present in the set of active peaks.
// It might have been removed if it ceased to be a peak due to a previous operation on a neighbor.
// If it's not in the set, skip processing it.
if (peak_indices.count(k) == 0) {
continue;
}
// If k is in the set, it's a valid peak to operate on.
// Remove k from the set because we are about to perform the operation, which destroys this peak.
peak_indices.erase(k);
// Perform the operation as described in the problem:
// Replace A[k] with min(A[k-1], A[k+1]) - 1.
ll val_left = A[k-1]; // Value of the left neighbor.
ll val_right = A[k+1]; // Value of the right neighbor.
// The new value for A[k] is one less than the minimum of its neighbors.
A[k] = min(val_left, val_right) - 1;
total_ops++; // Increment the total operations counter.
// After modifying A[k], the peak conditions for indices k-1, k, and k+1 might have changed.
// We need to re-evaluate these indices and update their status in the peak set and worklist.
// `update_peak_status` function handles boundaries and updates correctly.
update_peak_status(k - 1); // Check and update status for the element to the left of the original peak's left neighbor. Its peak condition depends on A[k-1]. The triplet is (A[k-2], A[k-1], A[k]). A[k] changed value.
update_peak_status(k); // Check and update status for index k itself. After the operation, A[k] is guaranteed not to be a peak because A[k] < A[k-1] and A[k] < A[k+1]. This call ensures it's removed from the set if somehow it was still there.
update_peak_status(k + 1); // Check and update status for the element to the right of the original peak. Its peak condition depends on A[k]. The triplet is (A[k], A[k+1], A[k+2]). A[k] changed value.
}
// After the loop finishes (no more peaks can be processed), output the total count of operations.
cout << total_ops << endl;
return 0;
}