Submission #1258667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258667		Sorting	Triple Peaks (IOI25_triples)	C++20	11 / 100	417 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 the LEFT end (i). H[i] = k - i.
    // For fixed i, k is forced: k = i + H[i].
    // Then j is forced by H[k] in at most two ways:
    //   (A) H[k] = k - j  -> j = k - H[k], require H[j] = j - i
    //   (B) H[k] = j - i  -> j = i + H[k], require H[j] = k - j
    for (int i = 0; i < N; ++i) {
        int k = i + H[i];
        if (k >= 0 && k < N) {
            int cnt = 0;
            int j1 = k - H[k];
            if (i < j1 && j1 < k && H[j1] == j1 - i) ++cnt;

            int j2 = i + H[k];
            if (j2 != j1 && i < j2 && j2 < k && H[j2] == k - j2) ++cnt;

            ans += cnt;
        }
    }

    // -------- Case 2: Max at the RIGHT end (k). H[k] = k - i.
    // Symmetric to case 1.
    for (int k = 0; k < N; ++k) {
        int i = k - H[k];
        if (i >= 0 && i < k) {
            int cnt = 0;
            int j1 = i + H[i];
            if (i < j1 && j1 < k && H[j1] == k - j1) ++cnt;

            int j2 = k - H[i];
            if (j2 != j1 && i < j2 && j2 < k && H[j2] == j2 - i) ++cnt;

            ans += cnt;
        }
    }

    // -------- Case 3: Max at the MIDDLE (j). H[j] = (j - i) + (k - j).
    //
    // Let D = H[j]. For any split s in {1..D-1}:
    //   left gap  = s
    //   right gap = D - s
    // i = j - s, k = j + (D - s)
    // We need {H[i], H[k]} = {s, D - s}.
    //
    // Iterating all s is too slow, so we use the standard small/large trick:
    // only iterate s up to B ~ sqrt(N). This checks any triple where the
    // smaller of the two gaps is <= B. For the remaining (both gaps > B),
    // they are handled implicitly via the “max at ends” cases above (fast),
    // plus a small extra loop below that covers the swapped orientation when
    // one of the endpoint heights is small.
    int B = max(1, (int) 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}
        if ((H[i] == a && H[k] == b) || (H[i] == b && H[k] == a)) return 1;
        return 0;
    };

    for (int j = 0; j < N; ++j) {
        int D = H[j];
        if (D <= 1) continue;
        int up = min(B, D - 1);
        // iterate only the smaller gap s (so s <= D - s) to avoid double counting
        up = min(up, D / 2);
        for (int s = 1; s <= up; ++s) {
            ans += check_pair(j, s);
        }
        // Also cover the case where the RIGHT gap is the smaller (<= B) but
        // right gap < left gap; that is equivalent to iterating s' = (D - s)
        // where s' <= B and s' < D - s'. To avoid overlap, we handle the
        // “right-small” side with strict inequality.
        int right_up = min(B, D - 1);
        for (int r = 1; r <= right_up; ++r) {
            if (r < D - r) { // strict to avoid double counting when gaps equal
                // right gap = r -> s = D - r
                ans += check_pair(j, D - r);
            }
        }
    }

    // -------- Extra safety: swapped-orientation when one endpoint height is small.
    //
    // Swapped middle-max means H[i] = (k - j) and H[k] = (j - i), i.e., endpoints' heights
    // equal the *opposite* gaps. Such triples are often already covered by the loops above,
    // but to be robust we add an O(B*N) sweep:
    //
    // For each small a = H[i] (1..B) and each k:
    //   i = k - (a + H[k])
    //   j = k - a
    // Check bounds and H[j] == a + H[k].
    //
    // This is linear in N for each small a, so O(B*N).
    for (int a = 1; a <= B; ++a) {
        for (int k = 0; k < N; ++k) {
            int i = k - (a + H[k]);
            if (i < 0 || i >= k) continue;
            int j = k - a;
            if (j <= i || j >= k) continue;
            if (H[i] != a) continue;
            if (H[j] == a + H[k]) {
                ++ans;
            }
        }
    }

    // The symmetric small-end on the right (small H[k]) — also O(B*N).
    for (int b = 1; b <= B; ++b) {
        for (int i = 0; i < N; ++i) {
            int k = i + H[i] + b;
            if (k <= i || k >= N) continue;
            int j = i + H[i];
            if (j <= i || j >= k) continue;
            if (H[k] != b) continue;
            if (H[j] == H[i] + b) {
                ++ans;
            }
        }
    }

    // Finally, middle-max *perfectly symmetric* (equal gaps) were touched multiple times.
    // Count each symmetric middle-max once and subtract duplicates.
    // Symmetric means: H[j] even, a = H[j]/2, i = j - a, k = j + a, and H[i] = H[k] = a.
    long long symmetric_mid = 0;
    for (int j = 0; j < N; ++j) {
        int D = H[j];
        if ((D & 1) == 0) {
            int a = D / 2;
            int i = j - a, k = j + a;
            if (i >= 0 && k < N && H[i] == a && H[k] == a) {
                ++symmetric_mid;
            }
        }
    }
    // We added symmetric triples more than once in our “middle” loops; keep exactly one copy.
    // The two small-gap passes can both hit the same symmetric triple, so subtract one of them.
    ans -= symmetric_mid;

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

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 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