#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct mst {
vector<vector<int>> st;
size_t sz;
mst(vector<int> a) {
sz = 1;
while (sz < a.size()) {
sz <<= 1;
}
st.resize(2 * sz);
for (int i = 0; i < a.size(); i++) {
st[sz + i].push_back(a[i]);
}
for (int i = sz - 1; i > 0; i--) {
st[i].resize(st[2 * i].size() + st[2 * i + 1].size());
ranges::merge(st[2 * i], st[2 * i + 1], st[i].begin());
}
}
int get_same(int l, int r, int v) {
l += sz; r += sz;
int res = 0;
while (l <= r) {
if (l & 1) {
res += ranges::upper_bound(st[l], v) - ranges::lower_bound(st[l], v);
l++;
}
if (~r & 1) {
res += ranges::upper_bound(st[r], v) - ranges::lower_bound(st[r], v);
r--;
}
l >>= 1;
r >>= 1;
}
return res;
}
};
ll count_triples(vector<int> h) {
int n = h.size();
vector<int> ff = h, ss = h;
vector<int> prev(n), next(n);
for (int i = 0; i < n; i++) {
ff[i] -= i;
ss[i] += i;
}
map<int, int> mp;
for (int i = 0; i < n; i++) {
if (mp.find(ff[i]) == mp.end()) {
prev[i] = -1;
} else {
prev[i] = mp[ff[i]];
}
mp[ff[i]] = i;
}
mp.clear();
for (int i = n - 1; i >= 0; i--) {
if (mp.find(ss[i]) == mp.end()) {
next[i] = n;
} else {
next[i] = mp[ss[i]];
}
mp[ss[i]] = i;
}
mst mst1(ff), mst2(ss);
ll ans = 0;
auto check1 = [&](int i, int j, int k) -> bool {
vector<int> x = {abs(i - j), abs(j - k), abs(k - i)}, y = {h[i], h[j], h[k]};
ranges::sort(x);
ranges::sort(y);
return x == y;
};
auto check2 = [&](int i, int j, int k) -> bool {
if (abs(k - i) == h[j] && abs(i - j) == h[k] && abs(j - k) == h[i]) return false;
return check1(i, j, k);
};
auto srt = [](tuple<int, int, int> t) -> tuple<int, int, int> {
vector<int> x = {get<0>(t), get<1>(t), get<2>(t)};
ranges::sort(x);
return {x[0], x[1], x[2]};
};
set<tuple<int, int, int>> simp;
for (int i = 0; i < n; i++) {
if (i - h[i] >= 0) {
int j = i - h[i];
if (j - h[j] >= 0) {
int l = j - h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (j + h[j] < n) {
int l = j + h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (i - h[j] >= 0) {
int l = i - h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (i + h[j] < n) {
int l = i + h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
}
if (i + h[i] < n) {
int j = i + h[i];
if (j - h[j] >= 0) {
int l = j - h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (j + h[j] < n) {
int l = j + h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (i - h[j] >= 0) {
int l = i - h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (i + h[j] < n) {
int l = i + h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
}
}
ans += simp.size();
simp.clear();
for (int i = 0; i < n; i++) {
if (mst1.get_same(0, i, ff[i]) < mst2.get_same(i, n - 1, ss[i])) {
int cur = prev[i];
while (cur != -1) {
if (i + h[cur] < n && check1(cur, i, i + h[cur])) {
ans++;
}
cur = prev[cur];
}
} else {
int cur = next[i];
while (cur != n) {
if (i - h[cur] >= 0 && check1(i - h[cur], i, cur)) {
ans++;
}
cur = next[cur];
}
}
}
return ans;
}
mt19937 mt(123);
vector<int> construct_range(int n, int _K) {
int D, CD;
if (n == 200000) {
D = 430;
CD = 200;
}
if (n == 100000) {
D = 252;
CD = 126;
}
if (n == 30000) {
D = 162;
CD = 80;
}
if (n == 5000) {
D = 62;
CD = 32;
}
if (n == 500) {
return {230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 40, 241, 242, 243, 244, 245, 246, 247, 248, 249, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 60, 221, 222, 223, 224, 225, 226, 227, 228, 229, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 40, 281, 202, 203, 204, 205, 206, 207, 208, 209, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 20, 261, 182, 303, 184, 185, 186, 187, 188, 189, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 2, 241, 162, 283, 164, 325, 166, 167, 168, 169, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 20, 221, 142, 263, 144, 305, 146, 347, 148, 149, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 2, 201, 122, 243, 124, 285, 126, 327, 128, 369, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 181, 102, 223, 104, 265, 106, 307, 108, 349, 70, 391, 72, 73, 74, 75, 76, 77, 78, 79, 80, 161, 82, 203, 84, 245, 86, 287, 88, 329, 50, 371, 52, 413, 54, 55, 56, 57, 58, 59, 60, 141, 62, 183, 64, 225, 66, 267, 68, 309, 8, 351, 10, 393, 6, 435, 2, 3, 4, 1, 2, 121, 8, 163, 6, 205, 4, 247, 6, 289, 2, 331, 2, 373, 4, 415, 2, 457, 2, 3, 20, 1, 2, 1, 2, 3, 4, 1, 2, 7, 8, 5, 6, 3, 4, 1, 2, 1, 6, 9, 4, 7, 6, 5, 4, 9, 2, 11, 2, 1, 6, 3, 2, 5, 4, 375, 2, 417, 22, 459, 2, 3, 4, 1, 2, 145, 6, 187, 6, 229, 4, 271, 50, 313, 48, 355, 46, 397, 44, 43, 42, 41, 40, 39, 38, 37, 36, 167, 34, 209, 32, 251, 30, 293, 72, 335, 70, 377, 68, 419, 66, 65, 64, 63, 62, 61, 60, 59, 58, 189, 56, 231, 54, 273, 60, 315, 94, 357, 92, 399, 90, 89, 2, 87, 86, 85, 84, 83, 82, 81, 80, 211, 78, 253, 76, 295, 86, 337, 116, 379, 114, 113, 112, 111, 22, 109, 108, 107, 106, 105, 104, 103, 102, 233, 100, 275, 98, 317, 2, 359, 138, 137, 136, 135, 134, 133, 44, 131, 130, 129, 128, 127, 126, 125, 124, 255, 122, 297, 120, 339, 2, 161, 160, 159, 158, 157, 156, 155, 66, 153, 152, 151, 150, 149, 148, 147, 146, 277, 144, 319, 142, 1, 1, 183, 182, 181, 180, 179, 178, 177, 88, 175, 174, 173, 172, 171, 170, 169, 168, 299, 166, 165, 164, 2, 1, 205, 204, 203, 202, 201, 200, 199, 22, 197, 196, 195, 194, 193, 192, 191, 190, 189, 188, 187, 186, 2, 1, 227, 226, 225, 224, 223, 222, 221, 44, 219, 218, 217, 216, 215, 214, 213, 212, 211, 210, 209, 208, 1, 2, 249, 248, 247, 246, 245, 244, 243, 22, 241, 240, 239, 238, 237, 236, 235, 234, 233, 232, 231, 230};
}
if (n == 20) {
vector<int> ans = {3, 3, 1, 2, 1, 4, 5, 2, 3, 3, 1, 2, 1, 4, 3, 2, 3, 1, 1, 2};
return ans;
}
n--;
vector<int> ans(n, 0);
for (int i = 0; i < CD; i++) {
for (int j = 0; j < D; j++) {
ans[i * D + j] = (n + 1) / 2 - D - i * D + j;
}
}
for (int i = 0; i < CD; i++) {
for (int j = 0; j < D; j++) {
ans[n - 1 - (i * (D + 2) + j)] = (n + 1) / 2 - D - i * D + j - 2 * i;
}
}
int cnt = 0;
vector<int> ch(n, -1);
for (int i = 0; i < CD; i++) {
for (int j = 0; j < CD; j++) {
int hui = (n - 1 + i * D - j * (D + 2)) / 2 - (ans[i * D] - ans[n - 1 - (j * (D + 2))]) / 2;
// if (hui >= CD * D && hui < n - CD * (D + 2)) {
cnt++;
ch[hui] = ans[i * D] + hui - i * D;
// }
}
}
for (int i = 0; i < n; i++) {
if (ch[i] != -1) {
ans[i] = ch[i];
}
}
for (int i = 0; i < n; i++) {
if (ans[i] == 0) {
ans[i] = ((i / 2) % 2 + 1) * 2;
}
ans[i] = max(min(ans[i], n - 1), 1);
}
return ans;
}
# | 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... |