Submission #1319295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319295		Rainmaker2627	Triple Peaks (IOI25_triples)	C++20	75.08 / 100	96 ms	31132 KiB

triples

#include "triples.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

long long count_triples(std::vector<int> H) {
    int N=H.size(), OFFSET=H.size(), ans=0;
    vector<vector<int>> sum(2*N+1, vector<int>()), diff(2*N+1, vector<int>());
    for (int i = 0; i < N; i++) {
        sum[i+H[i]].push_back(i);
        diff[i-H[i]+OFFSET].push_back(i);
    }

    for (int t = 0; t < N; t++) {
        {
            int i=t;
            int k=i-H[i];
            if (k<0 || H[k]>=H[i]) goto next;
            {
                int j=i-H[k];
                if (H[j]==j-k) ans++;
            } {
                int j=k+H[k];
                if (H[j]==i-j && i-j!=j-k) ans++;
            }
        } next: {
            int k=t;
            int i=H[k]+k;
            if (i>=N || H[i]>=H[k]) goto end;
            {
                int j=i-H[i];
                if (H[j]==j-k) ans++;
            } {
                int j=H[i]+k;
                if (H[j]==i-j && i-j!=j-k) ans++;
            }
        } end: continue;
    }

    for (int j = 0; j < N; j++) {
        for (int t = 0; t < sum[j].size(); t++) {
            int k=sum[j][t];
            if (k>=j) break;
            if (H[k]>=H[j]) continue;
            int Hi=H[j]-H[k];
            int i=Hi+j;
            if (i<N && H[i]==Hi && i-j!=j-k) ans++;
        }

        int sum_start=upper_bound(sum[j+H[j]].begin(), sum[j+H[j]].end(), j)-sum[j+H[j]].begin();
        int diff_end=lower_bound(diff[j-H[j]+OFFSET].begin(), diff[j-H[j]+OFFSET].end(), j)-diff[j-H[j]+OFFSET].begin();
        if (sum[j+H[j]].size()-sum_start < diff_end) {
            auto ref=sum[j+H[j]];
            for (int t = sum_start; t < ref.size(); t++) {
                int i=ref[t];
                int k=j-H[i];
                if (k<0) continue;
                if (H[k]+H[i]==H[j]) ans++;
            }
        } else {
            auto ref=diff[j-H[j]+OFFSET];
            for (int t = 0; t < diff_end; t++) {
                int k=ref[t];
                int i=H[k]+j;
                if (i>=N) continue;
                if (H[k]+H[i]==H[j]) ans++;
            }
        }
    }

    return ans;
}

std::vector<int> construct_range(int M, int K) {
    if (M==20 && K==30) {
        return {2, 3, 4, 1, 2, 1, 3, 1, 2, 1, 4, 3, 2, 3, 1, 1, 2, 1, 1, 3};
    }
}

Compilation message (stderr)

triples.cpp: In function 'std::vector<int> construct_range(int, int)':
triples.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
   78 | }
      | ^

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