| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1358217 | miubepbep | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
long long count_triples(vector<int> H) {
int N = (int)H.size();
vector<vector<int>> L(N), R(N);
// L[p]: các x sao cho tồn tại i = p-x, H[i] = x
// R[p]: các y sao cho tồn tại k = p+y, H[k] = y
for (int i = 0; i < N; i++) {
int x = H[i];
if (i + x < N) L[i + x].push_back(x);
if (i - x >= 0) R[i - x].push_back(x);
}
long long ans = 0;
int B = (int)sqrt(N) + 1;
vector<int> markL(N + 1, 0), markR(N + 1, 0);
int timer = 0;
// --------------------------------------------------
// 1) largest ở giữa
// --------------------------------------------------
for (int p = 0; p < N; p++) {
auto &A = L[p];
auto &Bv = R[p];
if (A.empty() || Bv.empty()) continue;
// Khả năng A: middle = p
{
++timer;
if ((int)A.size() < (int)Bv.size()) {
for (int y : Bv) markR[y] = timer;
for (int x : A) {
int need = H[p] - x;
if (need > 0 && need <= N && markR[need] == timer) ans++;
}
} else {
for (int x : A) markL[x] = timer;
for (int y : Bv) {
int need = H[p] - y;
if (need > 0 && need <= N && markL[need] == timer) ans++;
}
}
}
// Khả năng B: middle = q = p + y - x, q != p
long long prod = 1LL * A.size() * Bv.size();
if (prod <= 1LL * B * B) {
for (int x : A) {
for (int y : Bv) {
if (x == y) continue;
int q = p + y - x;
if (0 <= q && q < N && H[q] == x + y) ans++;
}
}
} else {
++timer;
for (int x : A) markL[x] = timer;
for (int y : Bv) markR[y] = timer;
for (int q = 0; q < N; q++) {
if (q == p) continue;
int s = H[q];
int d = q - p;
int numX = s - d;
int numY = s + d;
if (numX & 1) continue;
if (numY & 1) continue;
int x = numX / 2;
int y = numY / 2;
if (x <= 0 || y <= 0) continue;
if (x > N || y > N) continue;
if (markL[x] == timer && markR[y] == timer) ans++;
}
}
}
// --------------------------------------------------
// 2) largest ở trái
// --------------------------------------------------
for (int i = 0; i < N; i++) {
int s = H[i];
int k = i + s;
if (k >= N) continue;
int t = H[k];
if (0 < t && t < s) {
int j1 = i + t;
if (j1 > i && j1 < k && H[j1] == s - t) ans++;
int j2 = i + (s - t);
if (t != s - t && j2 > i && j2 < k && H[j2] == s - t) ans++;
}
}
// --------------------------------------------------
// 3) largest ở phải
// --------------------------------------------------
for (int k = 0; k < N; k++) {
int s = H[k];
int i = k - s;
if (i < 0) continue;
int t = H[i];
if (0 < t && t < s) {
int j1 = i + t;
if (j1 > i && j1 < k && H[j1] == s - t) ans++;
int j2 = i + (s - t);
if (t != s - t && j2 > i && j2 < k && H[j2] == s - t) ans++;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Input Part I theo sample grader:
// 1
// N
// H[0] H[1] ... H[N-1]
int part;
cin >> part;
if (part == 1) {
int N;
cin >> N;
vector<int> H(N);
for (int i = 0; i < N; i++) cin >> H[i];
cout << count_triples(H) << '\n';
}
return 0;
}