#include "triples.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; vector<int> construct_range(int M, int K) { // ll N = M; // vector<int> vf; // vf.push_back(1); // for (ll i=1;i<N;i++) { // vf.push_back(i); // } // return vf; vector<int> vf(M,M-1); vector<ll> v0; ll tsum = 0; ll cv = 2; while (tsum<(4*M)) { v0.push_back(cv); tsum += cv; cv += 2; } for (ll x: v0) { for (ll y: v0) { ll xf = (x+y)/2; ll yf = (y-x)/2; if (yf>0 && xf<M) { vf[xf]=min((ll)vf[xf],(ll)yf); } } } return vf; } long long count_triples(vector<int> H) { ll N = H.size(); ll ans = 0; //H[x]=z-x H[y]=z-y H[z]=y-x // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(z-x) && H[y]==(z-y) && H[z]==(y-x)) { // ans++; // } // } // } // } for (ll x=0;x<N;x++) { ll z = x+H[x]; if (z<N) { ll y=H[z]+x; if (y<N) { if ((H[y]+y)==z && x<y && y<z && (z-y)!=(y-x)) { ans++; } } } } //H[x]=z-x H[y]=y-x H[z]=z-y // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(z-x) && H[y]==(y-x) && H[z]==(z-y)) { // ans++; // } // } // } // } for (ll x=0;x<N;x++) { ll z = x+H[x]; if (z<N) { ll y = z-H[z]; if (y>=0) { if (H[y]==(y-x) && x<y && y<z) { ans++; } } } } //H[x]=y-x, H[y]=z-x, H[z]=z-y // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(y-x) && H[y]==(z-x) && H[z]==(z-y)) { // ans++; // } // } // } // } for (ll x=0;x<N;x++) { ll y=x+H[x]; if (y<N) { ll z = x+H[y]; if (z<N) { if (H[z]==(z-y) && x<y && y<z && (z-y)!=(y-x)) { ans++; } } } } //H[x]=y-x, H[y]=z-y, H[z]=z-x // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(y-x) && H[y]==(z-y) && H[z]==(z-x)) { // ans++; // } // } // } // } for (ll x=0;x<N;x++) { ll y=x+H[x]; if (y<N) { ll z = y+H[y]; if (z<N) { if (H[z]==(z-x) && x<y && y<z && (z-y)!=(y-x)) { ans++; } } } } //H[x]=z-y, H[y]=y-x, H[z]=z-x // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(z-y) && H[y]==(y-x) && H[z]==(z-x)) { // ans++; // } // } // } // } for (ll y=0;y<N;y++) { ll x = y-H[y]; if (x>=0) { ll z = y+H[x]; if (z<N) { if (H[z]==(z-x) && x<y && y<z) { ans++; } } } } //H[x]=z-y, H[y]=z-x, H[z]=y-x // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(z-y) && H[y]==(z-x) && H[z]==(y-x)) { // ans++; // } // } // } // } vector<ll> va[N]; vector<ll> vb[N]; for (ll x=0;x<N;x++) { if ((x+H[x])<N) { va[x+H[x]].push_back(x); } if ((x-H[x])>=0) { vb[x-H[x]].push_back(x); } } for (ll r=0;r<N;r++) { ll A = va[r].size(); ll B=vb[r].size(); if ((A*B)>=N) { for (ll x0=0;x0<N;x0++) { ll y0 = H[x0]; if ((x0+y0)%2==(r%2)) { ll x1 = (x0+y0+r)/2; ll y1 = (x0+y0-r)/2; ll x2 = (r+x0-y0)/2; ll y2 = (y0-x0+r)/2; if (x1<N && x1>=0 && x2<N && x2>=0) { if (H[x1]==y1 && H[x2]==y2) { ans++; } } } } } else { //manual: A*B for (ll xa: va[r]) { ll ya = H[xa]; for (ll xb: vb[r]) { ll yb = H[xb]; ll xf = xa+xb-r; ll yf = ya+yb; if (xf>=0 && xf<N) { if (H[xf]==yf) { ans++; } } } } } } return ans; }