Submission #1295765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295765		lucas110550	Triple Peaks (IOI25_triples)	C++20	Compilation error	0 ms	0 KiB

triples

#include <vector>
#include <unordered_map>
#include <algorithm>

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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccUbHhHh.o: in function `main':
grader.cpp:(.text.startup+0x197): undefined reference to `construct_range(int, int)'
collect2: error: ld returned 1 exit status