# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1250048 | testacc11 | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int part;
if(!(cin >> part)) return 0;
if(part != 1){
// This is Part I only.
return 0;
}
int N;
cin >> N;
vector<int> H(N);
for(int i = 0; i < N; i++){
cin >> H[i];
}
// Precompute:
// L1[j] = all i < j with i + H[i] == j (so H[i] = j - i)
// S[T] = all k with k + H[k] == T
vector<vector<int>> L1(N);
vector<vector<int>> S(N + N); // k+H[k] in [0..2N-2]
for(int i = 0; i < N; i++){
int j1 = i + H[i];
if(j1 < N) L1[j1].push_back(i);
int T = i + H[i];
S[T].push_back(i);
}
ll ans = 0;
// Main loop over the “middle” peak j
for(int j = 0; j < N; j++){
int hj = H[j];
// Case A: H[j] = d1 = j - i
// ⇒ i = j - H[j], check k = j + H[i], and H[k] == H[i]+H[j].
{
int i = j - hj;
if(i >= 0) {
int hi = H[i];
int k = j + hi;
if(k < N && hi + hj == H[k]) {
ans++;
}
}
}
// Case B: H[j] = d2 = k - j
// ⇒ k = j + H[j], check i = k - H[k], and H[i] == H[k] - H[j].
{
int k = j + hj;
if(k < N) {
int hk = H[k];
int i = k - hk;
if(i < j && i >= 0 && hk - hj == H[i]) {
ans++;
}
}
}
// Case C1: H[j] = d3 = (k - i), with H[i] = d1 = j - i
// ⇒ i in L1[j], then k = i + H[j], and check H[k] = d2 = H[j] - H[i].
for(int i : L1[j]) {
int hi = H[i];
int k = i + hj;
if(k > j && k < N && H[k] == hj - hi) {
ans++;
}
}
// Case C2: H[j] = d3 = (k - i), with H[k] = d1 = j - i
// ⇒ all k with k + H[k] = j + H[j] (so H[k] = (j+H[j]) - k = j - (k-j) = d1),
// then set i = k - H[j] and check H[i] = d2 = k - j.
int Tj = j + hj;
if(Tj < (int)S.size()){
for(int k : S[Tj]) {
if(k <= j) continue;
int i = k - hj;
if(i < j && i >= 0 && H[i] == k - j) {
ans++;
}
}
}
}
cout << ans << "\n";
return 0;
}