# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1250056 | testacc11 | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
// triples.cpp
#include <vector>
using namespace std;
using ll = long long;
// Part I: count all mythical triples in O(N) time and O(N) memory.
ll count_triples(const vector<int>& H) {
int N = H.size();
// L1[j] = all i<j such that H[i] = j-i
vector<vector<int>> L1(N);
// S[T] = all k such that k+H[k] = T
vector<vector<int>> S(2 * N);
for (int i = 0; i < N; i++) {
int t = i + H[i];
if (t < N) L1[t].push_back(i);
S[t].push_back(i);
}
ll ans = 0;
for (int j = 0; j < N; j++) {
int hj = H[j];
// Case A: H[j] = d1 = j - i
{
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
{
int k = j + hj;
if (k < N) {
int hk = H[k];
int i = k - hk;
if (i >= 0 && i < j && hk - hj == H[i])
ans++;
}
}
// Case C1: H[j] = d3, with H[i]=d1 and H[k]=d2
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, with H[k]=d1 and H[i]=d2
int Tj = j + hj;
if (Tj < (int)S.size()) {
for (int k : S[Tj]) {
if (k <= j) continue;
int i = k - hj;
if (i >= 0 && i < j && H[i] == k - j)
ans++;
}
}
}
return ans;
}
// Part II stub (if needed by grader)
vector<int> construct_range(int M, int K) {
return vector<int>(); // not used for Part I
}