제출 #1250182

#제출 시각아이디문제언어결과실행 시간메모리
1250182s4dzTriple Peaks (IOI25_triples)C++20
0 / 100
27 ms15684 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; //sub4: std::vector<int> construct_range(int M, int K) { return{}; } /*long long count_triples(vector<int> H) { int n = H.size(); ll ans = 0; for (int k = 0; k < n; k++) { int c = H[k]; int i = k - c; if (i < 0 || i >= n) continue; int a = H[i]; if (a > c - a) continue; int need = c - a; int j1 = i + a; int j2 = k - a; if (i < j1 && j1 < k && H[j1] == need) ans++; if (j2 != j1 && i < j2 && j2 < k && H[j2] == need) ans++; } return ans; }*/ ll count_triples(vector<int> H) { int N = H.size(); ll ans = 0; for (int i = 0; i < N; i++) { int k = i + H[i]; if (k >= N) continue; // if H[k] == j - i → j = i + H[k] { int j = i + H[k]; if (j > i && j < k && H[j] == k - j) ans++; } // if H[k] == k - j → j = k - H[k] { int j = k - H[k]; if (j > i && j < k && H[j] == j - i) ans++; } } for (int k = 0; k < N; k++) { int i = k - H[k]; if (i < 0) continue; { int j = i + H[i]; if (j > i && j < k && H[j] == k - j) ans++; } { int j = k - H[i]; if (j > i && j < k && H[j] == j - i) ans++; } } for (int i = 0; i < N; i++) { int j = i + H[i]; if (j >= N) continue; int k = i + H[j]; if (k < N && H[k] == k - j) ans++; } int T = int(sqrt(N)); vector<vector<int>> groups(2*N+1); for (int i = 0; i < N; i++) { int x = H[i] - i + N; groups[x].push_back(i); } for (int gx = 0; gx <= 2*N; gx++) { auto &vec = groups[gx]; if (vec.empty()) continue; int C = gx - N; if ((int)vec.size() <= T) { for (int a = 0; a < (int)vec.size(); a++) { for (int b = a+1; b < (int)vec.size(); b++) { int i = vec[a], j = vec[b]; int k = i + j + C; if (k < N && j < k && H[k] == j - i) ans++; } } } else { for (int k = 0; k < N; k++) { int sum = k - C; int diff = H[k]; if (((sum + diff) & 1) != 0) continue; int j = (sum + diff) >> 1; int i = j - diff; if (0 <= i && i < j && j < k) { if (H[i] - i == C && H[j] - j == C) ans++; } } } } return ans; }
#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...