| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1249444 | jtnydv25 | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "omp.h"
using namespace std;
#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif
long long count_triples(vector<int> H){
int n = H.size();
const int OFFSET = n;
vector<vector<int>> at_sum(2 * n + 1), at_diff(2 * n + 1);
for(int i = 0; i < n; i++){
at_sum[i + H[i]].push_back(i);
at_diff[i - H[i] + OFFSET].push_back(i);
}
int ans = 0;
// right-most is highest
for(int k = 0; k < n; k++){
int i = k - H[k];
if(i < 0 || H[i] >= H[k]) continue;
{
int j = k - H[i];
if(H[j] == j - i) ans++;
}
{
int j = i + H[i];
if(H[j] == k - j && k + i != 2 * j) ans++;
}
}
// left-most is highest
for(int i = 0; i < n; i++){
int k = i + H[i];
if(k >= n || H[k] >= H[i]) continue;
{
int j = k - H[k];
if(H[j] == j - i) ans++;
}
{
int j = i + H[k];
if(H[j] == k - j && k + i != 2 * j) ans++;
}
}
// middle is highest
for(int j = 0; j < n; j++){
for(int i: at_sum[j]){
if(H[i] >= H[j] || i >= j) continue;
int Hk = H[j] - H[i];
int k = j + Hk;
if(k < n && H[k] == Hk && H[i] != Hk) {
ans++;
}
}
if(sz(at_sum[j + H[j]]) < sz(at_diff[j - H[j] + OFFSET])){
for(int k: at_sum[j + H[j]]){
if(H[k] >= H[j] || k <= j) continue;
int i = j - H[k];
if(i < 0) continue;
if(H[i] + H[k] == H[j]) ans++;
}
} else{
for(int i: at_diff[j - H[j] + OFFSET]){
if(H[i] >= H[j] || i >= j) continue;
int k = j + H[i];
if(k >= n) continue;
if(H[k] + H[i] == H[j]) ans++;
}
}
}
return ans;
}