| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1250051 | testacc11 | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <vector>
using namespace std;
using ll = long long;
// Part I
ll count_triples(const vector<int>& H) {
int N = H.size();
vector<vector<int>> L1(N);
vector<vector<int>> S(2*N);
for(int i = 0; i < N; i++){
int j1 = i + H[i];
if(j1 < N) L1[j1].push_back(i);
int T = i + H[i];
S[T].push_back(i);
}
ll ans = 0;
for(int j = 0; j < N; j++){
int hj = H[j];
// Case A
int i = j - hj;
if(i >= 0){
int hi = H[i], k = j + hi;
if(k < N && hi + hj == H[k]) ans++;
}
// Case B
int k = j + hj;
if(k < N){
int hk = H[k], ii = k - hk;
if(ii < j && ii >= 0 && hk - hj == H[ii]) ans++;
}
// Case C1
for(int ii: L1[j]){
int hi = H[ii], kk = ii + hj;
if(kk > j && kk < N && H[kk] == hj - hi) ans++;
}
// Case C2
int Tj = j + hj;
if(Tj < (int)S.size()){
for(int kk: S[Tj]){
if(kk <= j) continue;
int ii = kk - hj;
if(ii < j && ii >= 0 && H[ii] == kk - j) ans++;
}
}
}
return ans;
}
// Part II (if you’re also doing output‐only; otherwise you can leave this unimplemented)
vector<int> construct_range(int M, int K) {
// your construction here, e.g. a simple increasing sequence:
int N = min(M, K+2); // placeholder
vector<int> H(N);
for(int i = 0; i < N; i++) H[i] = 1;
return H;
}