| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1250720 | thegamercoder19 | Triple Peaks (IOI25_triples) | C++17 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <numeric>
#include <map>
// Function to solve Part I of the IOI 2025 "Triple Peaks" problem.
long long count_mythical_triples(int N, const std::vector<int>& H) {
long long count = 0;
// We analyze all 6 permutations of {H[i], H[j], H[k]} vs {a, b, a+b}
// where a = j-i, b = k-j, a+b = k-i.
// We must ensure 0 <= i < j < k < N for all triples.
// === Part 1: Simple cases solvable with a single loop ===
// These are cases where fixing `i` allows direct calculation of `j` and `k`.
for (int i = 0; i < N; ++i) {
// Case 1: H[i]=a, H[j]=b, H[k]=a+b
if (H[i] > 0) {
int j = i + H[i];
if (j > i && j < N && H[j] > 0) {
int k = j + H[j];
if (k > j && k < N) {
if (H[k] == H[i] + H[j]) {
count++;
}
}
}
}
// Case 2: H[i]=a, H[j]=a+b, H[k]=b
if (H[i] > 0) {
int j = i + H[i];
if (j > i && j < N) {
// From H[j]=a+b and H[i]=a, we must have H[j] > H[i]
if (H[j] > H[i]) {
int k = i + H[j];
if (k > j && k < N) {
if (H[k] == H[j] - H[i]) {
count++;
}
}
}
}
}
// Case 5: H[i]=a+b, H[j]=a, H[k]=b
if (H[i] > 0) {
int k = i + H[i];
if (k > i && k < N && H.size() > 1) { // H needs to be big enough for j
// We need to find j such that j=i+H[j]. This is not a direct calculation.
// Let's re-evaluate the equations.
// H[i]=k-i, H[j]=j-i, H[k]=k-j
// From H[j]=j-i -> j is determined by i.
// Let's check: j = i + H[j]. This is not direct.
// Instead, from H[k]=k-j we get j=k-H[k].
int j = k - H[k];
if (j > i && j < k) {
if (H[i] == H[j] + H[k]) { // Check the a+b relationship
count++;
}
}
}
}
}
// === Part 2: Complex cases requiring maps ===
// Case 3: H[i]=b, H[j]=a, H[k]=a+b
// Conditions: j-H[j] = i and k = j+H[i] and H[k]=H[i]+H[j]
std::map<int, std::vector<int>> f_inverse; // Stores j for a given i = j-H[j]
for(int j=0; j<N; ++j) {
if(j - H[j] >= 0) {
f_inverse[j - H[j]].push_back(j);
}
}
for(int i=0; i<N; ++i) {
if(f_inverse.count(i)) {
for(int j : f_inverse[i]) {
if(i < j) {
int k = j + H[i];
if(k > j && k < N && H[k] == H[i] + H[j]) {
count++;
}
}
}
}
}
// Case 4: H[i]=b, H[j]=a+b, H[k]=a
// Conditions: k-H[k] = i+H[i]
std::map<int, std::vector<int>> f_vals; // Stores k for a given val = k-H[k]
for (int k = 0; k < N; ++k) {
f_vals[k - H[k]].push_back(k);
}
for (int i = 0; i < N; ++i) {
int g_val = i + H[i];
if (f_vals.count(g_val)) {
for (int k : f_vals[g_val]) {
if (i < k) {
int j = k - H[i];
if (i < j && j < k && H[j] == H[i] + H[k]) {
count++;
}
}
}
}
}
// Case 6: H[i]=a+b, H[j]=b, H[k]=a
// Conditions: j+H[j] = i+H[i] and k = i+H[i] and H[k]=H[i]-H[j]
std::map<int, std::vector<int>> g_vals; // Stores indices i for a given val = i+H[i]
for(int j=0; j<N; ++j) {
int val = j + H[j];
if(g_vals.count(val)) {
for(int i : g_vals[val]) {
// We have i < j with i+H[i] = j+H[j]
int k = i + H[i];
if(k > j && k < N) {
if (H[i] > H[j] && H[k] == H[i] - H[j]) {
count++;
}
}
}
}
g_vals[val].push_back(j);
}
return count;
}
int main() {
// Fast I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read input N
int N;
std::cin >> N;
// Read mountain heights
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
std::cin >> H[i];
}
// Calculate and print the result
long long result = count_mythical_triples(N, H);
std::cout << result << std::endl;
return 0;
}