#include <bits/stdc++.h>
using namespace std;
long long count_triples(vector<int> H) {
const int N = (int)H.size();
long long ans = 0;
// Case 1: Max at LEFT end (i). H[i] = k - i, so k = i + H[i].
for (int i = 0; i < N; ++i) {
int k = i + H[i];
if (k >= 0 && k < N) {
int j1 = k - H[k];
if (i < j1 && j1 < k && H[j1] == j1 - i) ++ans;
int j2 = i + H[k];
if (j2 != j1 && i < j2 && j2 < k && H[j2] == k - j2) ++ans;
}
}
// Case 2: Max at RIGHT end (k). H[k] = k - i, so i = k - H[k].
for (int k = 0; k < N; ++k) {
int i = k - H[k];
if (i >= 0 && i < k) {
int j1 = i + H[i];
if (i < j1 && j1 < k && H[j1] == k - j1) ++ans;
int j2 = k - H[i];
if (j2 != j1 && i < j2 && j2 < k && H[j2] == j2 - i) ++ans;
}
}
// Case 3: Max at MIDDLE (j): H[j] = (j - i) + (k - j).
// Count only when the smaller gap <= B using a small/large split.
int B = max(1, (int)std::sqrt((double)N) + 1);
auto check_pair = [&](int j, int s) -> int {
int D = H[j];
if (s <= 0 || s >= D) return 0;
int i = j - s;
int k = j + (D - s);
if (i < 0 || k >= N) return 0;
int a = s, b = D - s;
// {H[i], H[k]} must be {a, b}
return ((H[i] == a && H[k] == b) || (H[i] == b && H[k] == a)) ? 1 : 0;
};
for (int j = 0; j < N; ++j) {
int D = H[j];
if (D <= 1) continue;
// Left gap is the smaller (s <= D - s) and s <= B
int up_left = min({B, D - 1, D / 2});
for (int s = 1; s <= up_left; ++s) {
ans += check_pair(j, s);
}
// Right gap is the smaller: r = D - s <= B with r < D - r <=> r < D/2
int up_right = min(B, D - 1);
for (int r = 1; r <= up_right && r < D - r; ++r) {
ans += check_pair(j, D - r);
}
}
return ans;
}
std::vector<int> construct_range(int M, int K) { return {};}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |