#include "triples.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> H;
ll n;
bool check(ll i,ll j,ll k){
if(i<0||j<0||k<0||i>=n||j>=n||k>=n)return 0;
ll s1[3],s2[3];
s1[0]=(abs(j-i));
s1[1]=(abs(k-i));
s1[2]=(abs(j-k));
sort(s1,s1+3);
if(s1[0]==0)return 0;
s2[0]=(H[i]);
s2[1]=(H[j]);
s2[2]=(H[k]);
sort(s2,s2+3);
return s1[0]==s2[0]&&s1[1]==s2[1]&&s1[2]==s2[2];
}
ll sub4(){
ll ans=0;
for(int i=n-1;i>1;i--){
ll x2=i-H[i];
if(x2<0)continue;
ll x3=x2+H[x2],x4=i-H[x2];
if(x3<i && i-x3==H[x3])ans++;
if(x3!=x4)
if(x4>x2 && x4-x2==H[x4])ans++;
}
return ans;
}
ll sub2(){
ll ans=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<=i+20;j++){
for(int k=j+1;k<n&&k<i+20;k++){
ans+=check(i,j,k);
}
}
}
return ans;
}
ll sub3(){
ll ans=0;
for(ll i=0;i<n;i++){
//Check M a b
while(1){
ll x2=i+H[i];
if(x2>=n)break;
ll x3=x2-H[x2],x4=i+H[x2];
if(x3>i && x3-i==H[x3])ans++;
if(x3!=x4)
if(x4<x2 && x2-x4==H[x4])ans++;
break;
}
//check a b M
while(1){
ll x2=i-H[i];
if(x2<0)break;
ll x3=x2+H[x2],x4=i-H[x2];
if(x3<i && i-x3==H[x3])ans++;
if(x3!=x4)
if(x4>x2 && x4-x2==H[x4])ans++;
break;
}
//check a M b
ll l=max(0LL,i-H[i]+1);
ll r=min(i,n-H[i]);
for(int j=l;j<r;j++){
ll x3=j+H[i];
if(H[j]==i-j&&H[x3]==x3-i)ans++;
else if(H[x3]==i-j&&H[j]==x3-i)ans++;
}
}
return ans;
}
ll count_triples(vector<int> h) {
n=h.size();
H=h;
return sub3();
}
vector<int> construct_range(int M, int K) {
vector<int> a;
for(int i=0;i<M;i++){
if(i%3)a.push_back(1);
else a.push_back(2);
}
return a;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |