#include "triples.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
using B = bitset<50000>;
B mp[100000];
long long count_triples(std::vector<int> H) {
int N = H.size();
ll ans = 0;
auto check = [&](int i, int j, int k) -> int { // i-ni hamgiin ondor
if (i < 0 || j < 0 || k < 0 || i >= N || j >= N || k >= N) return 0;
if (H[j] > H[i] || H[k] > H[i]) return 0;
vector<int> a{H[i], H[j], H[k]};
vector<int> b{abs(i - j), abs(i - k), abs(j - k)};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
return a == b;
};
FOR(i, 0, N - 1) {
if (i - H[i] >= 0) {
int j = i - H[i];
ans += check(i, j, i - H[j]);
if (i - H[j] != j + H[j]) ans += check(i, j, j + H[j]);
}
if (i + H[i] < N) {
int j = i + H[i];
ans += check(i, j, i + H[j]);
if (i + H[j] != j - H[j]) ans += check(i, j, j - H[j]);
}
}
FOR(j, 0, N - 1) {
int i = j + H[j];
if (i >= N) continue;
int k = j + H[i];
if (i < k && k < N && H[j] != H[k]) {
ans += check(i, j, k);
}
}
FOR(k, 0, N - 1) {
if (k - H[k] >= 0) ans += (mp[H[k] + k] & (mp[k - H[k]] << H[k])).count();
mp[k + H[k]][k] = 1;
}
return ans;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
# | 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... |