Submission #1254206

#TimeUsernameProblemLanguageResultExecution timeMemory
1254206TrendBattlesTriple Peaks (IOI25_triples)C++17
35.17 / 100
1119 ms1968 KiB
#include "triples.h" #include <bits/stdc++.h> using namespace std; using lli = int64_t; long long count_triples(vector <int> H) { int N = (int) H.size(); lli ans = 0; for (int iter = 1; iter <= 2; ++iter) { for (int i = 0; i < N; ++i) { if (i < H[i]) continue; int p = i - H[i]; if (H[p] >= H[i]) continue; ans += H[p + H[p]] == H[i] - H[p]; if (H[i] != H[p] * 2) ans += H[i - H[p]] == H[i] - H[p]; } reverse(H.begin(), H.end()); } if (is_sorted(H.begin(), H.end())) return ans; for (int i = 0; i < N; ++i) { if (i + H[i] >= N) continue; int j = i + H[i]; if (H[j] > H[i]) ans += H[j + H[j] - H[i]] == H[j] - H[i]; } int max_len = *max_element(H.begin(), H.end()) * 2; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < min(i + max_len, N); ++j) { if (j - i == H[i] + H[j]) { ans += H[i + H[j]] == H[i] + H[j]; } } } for (int i = 0; i < N; ++i) { if (H[i] % 2) continue; int half_len = H[i] / 2; ans -= i >= half_len and H[i - half_len] == half_len and i + half_len < N and H[i + half_len] == half_len; } return ans; } vector<int> construct_range(int M, int K) { return {1, 1, 2}; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...