Submission #1258668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258668		Sorting	Triple Peaks (IOI25_triples)	C++20	17 / 100	249 ms	1984 KiB

triples

#include <bits/stdc++.h>
using namespace std;

long long count_triples(vector<int> H) {
    const int N = (int)H.size();
    long long ans = 0;

    // Case 1: Max at LEFT end (i). H[i] = k - i, so k = i + H[i].
    for (int i = 0; i < N; ++i) {
        int k = i + H[i];
        if (k >= 0 && k < N) {
            int j1 = k - H[k];
            if (i < j1 && j1 < k && H[j1] == j1 - i) ++ans;
            int j2 = i + H[k];
            if (j2 != j1 && i < j2 && j2 < k && H[j2] == k - j2) ++ans;
        }
    }

    // Case 2: Max at RIGHT end (k). H[k] = k - i, so i = k - H[k].
    for (int k = 0; k < N; ++k) {
        int i = k - H[k];
        if (i >= 0 && i < k) {
            int j1 = i + H[i];
            if (i < j1 && j1 < k && H[j1] == k - j1) ++ans;
            int j2 = k - H[i];
            if (j2 != j1 && i < j2 && j2 < k && H[j2] == j2 - i) ++ans;
        }
    }

    // Case 3: Max at MIDDLE (j): H[j] = (j - i) + (k - j).
    // Count only when the smaller gap <= B using a small/large split.
    int B = max(1, (int)std::sqrt((double)N) + 1);

    auto check_pair = [&](int j, int s) -> int {
        int D = H[j];
        if (s <= 0 || s >= D) return 0;
        int i = j - s;
        int k = j + (D - s);
        if (i < 0 || k >= N) return 0;
        int a = s, b = D - s;
        // {H[i], H[k]} must be {a, b}
        return ((H[i] == a && H[k] == b) || (H[i] == b && H[k] == a)) ? 1 : 0;
    };

    for (int j = 0; j < N; ++j) {
        int D = H[j];
        if (D <= 1) continue;

        // Left gap is the smaller (s <= D - s) and s <= B
        int up_left = min({B, D - 1, D / 2});
        for (int s = 1; s <= up_left; ++s) {
            ans += check_pair(j, s);
        }

        // Right gap is the smaller: r = D - s <= B with r < D - r  <=>  r < D/2
        int up_right = min(B, D - 1);
        for (int r = 1; r <= up_right && r < D - r; ++r) {
            ans += check_pair(j, D - r);
        }
    }

    return ans;
}
std::vector<int> construct_range(int M, int K) { return {};}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 6 / 6
• Subtask 3: 0 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5