제출 #1250194

#제출 시각아이디문제언어결과실행 시간메모리
1250194s4dz3개의 봉우리 (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; { int j = i + H[k]; if(j > i && j < k && H[j] == k - j) ans++; } { 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 B = int(sqrt(N)); vector<vector<int>> groups(2*N + 1); for(int i = 0; i < N; i++) { int key = H[i] - i + N; groups[key].push_back(i); } for(int key = 0; key <= 2*N; key++) { auto &v = groups[key]; if(v.empty()) continue; int C = key - N; if((int)v.size() <= B) { for(int a = 0; a < (int)v.size(); a++) { for(int b = a+1; b < (int)v.size(); b++) { int i = v[a], j = v[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 && 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...