Submission #1256121

#TimeUsernameProblemLanguageResultExecution timeMemory
1256121TurkhuuTriple Peaks (IOI25_triples)C++20
34 / 100
519 ms284692 KiB
#include "triples.h" #include <bits/stdc++.h> #define FOR(i, a, b) for (auto i = (a); i <= (b); i++) #define ROF(i, a, b) for (auto i = (a); i >= (b); i--) using namespace std; using ll = long long; using B = bitset<50000>; B mp[100000]; long long count_triples(std::vector<int> H) { int N = H.size(); ll ans = 0; auto check = [&](int i, int j, int k) -> int { // i-ni hamgiin ondor if (i < 0 || j < 0 || k < 0 || i >= N || j >= N || k >= N) return 0; if (H[j] > H[i] || H[k] > H[i]) return 0; vector<int> a{H[i], H[j], H[k]}; vector<int> b{abs(i - j), abs(i - k), abs(j - k)}; sort(a.begin(), a.end()); sort(b.begin(), b.end()); return a == b; }; FOR(i, 0, N - 1) { if (i - H[i] >= 0) { int j = i - H[i]; ans += check(i, j, i - H[j]); if (i - H[j] != j + H[j]) ans += check(i, j, j + H[j]); } if (i + H[i] < N) { int j = i + H[i]; ans += check(i, j, i + H[j]); if (i + H[j] != j - H[j]) ans += check(i, j, j - H[j]); } } FOR(j, 0, N - 1) { int i = j + H[j]; if (i >= N) continue; int k = j + H[i]; if (i < k && k < N && H[j] != H[k]) { ans += check(i, j, k); } } FOR(k, 0, N - 1) { if (k - H[k] >= 0) ans += (mp[H[k] + k] & (mp[k - H[k]] << H[k])).count(); mp[k + H[k]][k] = 1; } return ans; } std::vector<int> construct_range(int M, int K) { return {1, 1, 1}; }
#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...