| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1249472 | bronze_coder | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
long long count_triples(vector<int> H){
int n = H.size();
long long count = 0;
for(int i=0;i<n;i++){
int a = H[i];
int j = i+a;
if(j<n){
int k;
k = j+H[j];
if(i<k&&k<n&&k!=j&&k-i==H[k]){
count++;
}
k = i+H[j];
if(i<k&&k<n&&k!=j&&max(k-j,j-k)==H[k]&&k!=j+H[i]){
count++;
}
k = j-H[j];
if(i<k&&k<n&&k!=j&&k-i==H[k]&&k!=i+H[j]){
count++;
}
}
j = i-a;
if(j>=0){
int k = i+H[j];
if(k<n&&i-j!=H[j]&&k>j&&k-j==H[k]){
count++;
}
}
}
vector<vector<int>> heights1(2*n);
vector<vector<int>> heights2(2*n);
for(int i=0;i<n;i++){
heights1[i+H[i]].push_back(i);
heights2[i-H[i]+n].push_back(i);
}
int m1 = 0;
int m2 = 0;
for(int i=0;i<2*n;i++){
int s1 = heights1[i].size();
int s2 = heights2[i].size();
m1 = max(m1,s1);
m2 = max(m2,s2);
}
if(m1<m2){
for(int a=0;a<2*n;a++){
for(int i1=0;i1<heights1[a].size();i1++){
for(int j1=i1+1;j1<heights1[a].size();j1++){
int j = heights1[a][i1];
int k = heights1[a][j1];
int i = k-H[j];
if(i>=0&&H[i]==k-j){
count++;
}
}
}
}
}
else{
for(int a=0;a<2*n;a++){
for(int i1=0;i1<heights2[a].size();i1++){
for(int j1=i1+1;j1<heights2[a].size();j1++){
int i = heights2[a][i1];
int j = heights2[a][j1];
int k = H[i]+j;
if(k<n&&H[k]==j-i){
count++;
}
}
}
}
}
return count;
}