#include "triples.h"
#include <bits/stdc++.h>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
using namespace std;
vector<int> a;
bool ok(int i , int j , int k){
vector<int> X = {j - i , k - j , k - i};
vector<int> Y = {a[i] , a[j] , a[k]};
sort(all(X)); sort(all(Y));
bool check = true;
for (int id = 0 ; id < 3 ; id++){
if (X[id] != Y[id]) return false;
}
return true;
}
namespace sub5{
const int maxN = int(2e5)+7;
long long cnt[2 * maxN] , A[maxN];
long long solve(){
set<pair<int , pair<int , int>>> st;
int n = sz(a);
//i , j , k
for (int i = 0 ; i < n ; i++){
int j = i + a[i];
if (j >= n) continue;
int k = j + a[j];
if (k >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
//i , k , j
for (int i = 0 ; i < n ; i++){
int j = i + a[i];
if (j >= n) continue;
int k = i + a[j];
if (k >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
//j , i , k
for (int j = 0 ; j < n ; j++){
int i = j - a[j];
if (i < 0) continue;
int k = j + a[i];
if (k >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
//j , k , i
for (int j = 0 ; j < n ; j++){
int i = j - a[j];
if (i < 0) continue;
int k = i + a[i];
if (k >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
//k , j , i
for (int i = 0 ; i < n ; i++){
int k = i + a[i];
if (k >= n) continue;
int j = i + a[k];
if (j >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
long long ans = sz(st);
//k , i , j
memset(cnt , 0 , sizeof(cnt));
for (int j = n - 1 ; j >= 0 ; j--){
A[j] = cnt[j + a[j]];
cnt[j + a[j]]++;
}
memset(cnt , 0 , sizeof(cnt));
for (int i = n - 1 ; i >= 0 ; i--){
ans += cnt[a[i] - i + maxN];
cnt[a[i] - i + maxN] += A[i];
}
for (int j = 0 ; j < n ; j++){
if (a[j]&1) continue;
int i = j - a[j] / 2;
int k = j + a[j] / 2;
if (i < 0 || k >= n) continue;
if (ok(i , j , k)) ans--;
}
return ans;
}
}
long long count_triples(vector<int> h){
a = h;
return sub5::solve();
}
vector<int> construct_range(int m , int k) {
return {1 , 1 , 1};
}
// int main(){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("templete.inp" , "r" , stdin);
// freopen("templete.out" , "w" , stdout);
// int n; cin >> n;
// vector<int> h(n);
// for (int &x : h) cin >> x;
// cout << count_triples(h) << "\n";
// return 0;
// }
# | 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... |