#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 = 1; // ll cv = 90000; // while (tsum<(M)) { // v0.push_back(tsum); // //cout << "tsum="<<tsum<<"\n"; // 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); // //cout << "xf="<<xf<<", yf="<<yf<<"\n"; // } // } // } // return vf; // } vector<int> cr2(int M, int K, ll cvr) { // 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 = 1; ll cv = cvr; while (tsum<(M)) { v0.push_back(tsum); //cout << "tsum="<<tsum<<"\n"; 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); //cout << "xf="<<xf<<", yf="<<yf<<"\n"; } } } return vf; } vector<int> construct_range(int M, int K) { ll cvr = 2; return cr2(M,K,cvr); } 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; } ll ct2(vector<int> H) { ll N = H.size(); ll ans = 0; 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; }