#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);
}
for(int i=0;i<n;i++){
int s1 = heights1[i+H[i]].size();
int s2 = heights2[i-H[i]+n].size();
if(s1<s2){
for(int j:heights1[i+H[i]]){
if(j>i){
int k = i-H[j];
if(k>=0&&k<n&&j-i==H[k]){
count++;
}
}
}
}
else{
for(int j:heights2[i-H[i]+n]){
if(j<i){
int k = j+H[i];
if(k>=0&&k<n&&i-j==H[k]){
count++;
}
}
}
}
}
return count;
}
vector<int> construct_range(int m, int k){
if(m==20){
return {2,1,1,3,2,3,4,1,2,1,3,1,2,1,4,3,2,3,1,1};
}
else{
vector<int> x;
vector<int> y;
int n = 200;
while(16*n*n+2*n>m){
n--;
}
vector<int> l(16*n*n+2*n,1);
for(int i=0;i<16*n*n+2*n;i++){
if(i%3==0){
l[i] = 2;
}
}
for(int i=0;i<n;i++){
x.push_back(i);
y.push_back(i);
}
for(int i=0;i<3*n;i++){
x.push_back(4*n*(i+1));
}
for(int i=0;i<n;i++){
y.push_back((4*n+1)*(i+1)+n-1);
}
for(int i=0;i<4*n;i++){
for(int j=0;j<2*n;j++){
if(i>=n||j>=n){
l[x[i]-y[j]+(4*n*n+2*n-1)] = x[i]+y[j]-(n-1);
}
}
}
return l;
}
}
# | 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... |