| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1295767 | lucas110550 | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <unordered_map>
#include <algorithm>
std::vector<int> construct_range(int M, int K) {
vector<int> mm;
mm.push_back(0);
return mm;
}
long long count_triples(std::vector<int> H) {
int n = (int)H.size();
std::unordered_map<int, std::vector<int>> groups1;
// Build groups1: d_val -> list of k
for (int k = 0; k < n; ++k) {
int d_val = k - H[k];
if (d_val >= 0) {
groups1[d_val].push_back(k);
}
}
// Sort each group's list
for (auto &p : groups1) {
std::sort(p.second.begin(), p.second.end());
}
long long total = 0;
// -------- First big loop (corresponds to first Python for-block) --------
for (const auto &p : groups1) {
int i = p.first;
if (i < 0 || i >= n) continue;
const std::vector<int> &L = p.second;
auto it = std::upper_bound(L.begin(), L.end(), i); // bisect_right
for (; it != L.end(); ++it) {
int k = *it;
if (k >= n) break;
int M = k - i;
if (M < 2) continue;
int required = M - H[i];
if (required < 1 || required > M - 1) continue;
int count_triple = 0;
int j1 = i + H[i];
if (j1 < k && j1 < n && H[j1] == required) {
count_triple++;
}
if (required != H[i]) {
int j2 = i + required;
if (j2 < k && j2 < n && H[j2] == required) {
count_triple++;
}
}
total += count_triple;
}
}
// -------- Second big loop --------
for (int i = 0; i < n; ++i) {
int M = H[i];
if (M < 2) continue;
int k = i + M;
if (k >= n) continue;
if (H[k] < 1 || H[k] >= M) continue;
int required = M - H[k];
int count_triple = 0;
int j1 = i + required;
if (j1 < k && j1 < n && H[j1] == required) {
count_triple++;
}
if (required != H[k]) {
int j2 = i + H[k];
if (j2 != j1 && j2 < k && j2 < n && H[j2] == required) {
count_triple++;
}
}
total += count_triple;
}
// -------- Third big loop --------
for (int i = 0; i < n; ++i) {
int d = i + H[i];
if (d < 0 || d >= n) continue;
auto it_group = groups1.find(d);
if (it_group == groups1.end()) continue;
const std::vector<int> &L = it_group->second;
auto it = std::upper_bound(L.begin(), L.end(), d); // bisect_right
for (; it != L.end(); ++it) {
int k = *it;
if (k >= n) break;
int M = k - i;
if (M < 2) continue;
int j1 = d;
int j2 = k - d + i;
int count_triple = 0;
if (0 <= j1 && j1 < k && j1 < n && H[j1] == M) {
count_triple++;
}
if (0 <= j2 && j2 < k && j2 < n && j2 != j1 && H[j2] == M) {
count_triple++;
}
total += count_triple;
}
}
return total;
}