Submission #1302488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302488		regulardude6	Triple Peaks (IOI25_triples)	C++20	2.65 / 100	24 ms	24184 KiB

triples

#include "triples.h"
#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);

    for (int i = 0; i < N; i++) {
        int j = i + H[i];
        if (j >= 0 && j < N) L[j].push_back(H[i]);
    }
    for (int k = 0; k < N; k++) {
        int j = k - H[k];
        if (j >= 0 && j < N) R[j].push_back(H[k]);
    }

    long long ans = 0;

    for (int i = 0; i < N; i++) {
        int d = H[i];
        int k = i + d;
        if (k >= N) continue;
        int t = H[k];
        if (1 <= t && t < d) {
            int j1 = i + t;
            if (j1 < k && H[j1] == d - t) ans++;
            int j2 = i + (d - t);
            if (j2 != j1 && j2 < k && H[j2] == t) ans++;
        }
    }

    for (int k = 0; k < N; k++) {
        int d = H[k];
        int i = k - d;
        if (i < 0) continue;
        int t = H[i];
        if (1 <= t && t < d) {
            int j1 = i + t;
            if (j1 < k && H[j1] == d - t) ans++;
            int j2 = i + (d - t);
            if (j2 != j1 && j2 < k && H[j2] == t) ans++;
        }
    }

    for (int j = 0; j < N; j++) {
        int d = H[j];
        auto &A = L[j];
        auto &B = R[j];
        if (A.empty() || B.empty()) continue;

        if (A.size() <= B.size()) {
            unordered_map<int,int> mp;
            mp.reserve(A.size() * 2 + 1);
            for (int a : A) mp[a]++;
            for (int b : B) {
                int need = d - b;
                auto it = mp.find(need);
                if (it != mp.end()) ans += it->second;
            }
        } else {
            unordered_map<int,int> mp;
            mp.reserve(B.size() * 2 + 1);
            for (int b : B) mp[b]++;
            for (int a : A) {
                int need = d - a;
                auto it = mp.find(need);
                if (it != mp.end()) ans += it->second;
            }
        }
    }

    return ans;
}

vector<int> construct_range(int M, int K) {
    int N = max(3, min(M, 200000));
    vector<int> H(N, 1);
    for (int i = 0; i < N; i++) H[i] = min(N - 1, max(1, (i % 2) + 1));
    return H;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 1.5 / 5
• Subtask 8: 0.6225 / 5
• Subtask 9: 0.2499 / 5
• Subtask 10: 0.1071 / 5
• Subtask 11: 0.125 / 5
• Subtask 12: 0.0417 / 5