제출 #1264495

#제출 시각아이디문제언어결과실행 시간메모리
1264495rainboyTriple Peaks (IOI25_triples)C++20
70 / 100
89 ms31304 KiB
/* discussed with lunchbox */ #include "triples.h" #include <cstdlib> #include <iostream> using namespace std; typedef vector<int> vi; const int N = 200000; int *ej[N * 3], eo[N * 3]; void append(int i, int j) { int o = eo[i]++; if (o >= 2 && (o & o - 1) == 0) ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]); ej[i][o] = j; } char used[N * 3]; long long count_triangles(vi aa, int n) { for (int i = 0; i < n * 3; i++) ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0; for (int i = 0; i < n; i++) { int l = n + i - aa[i], r = n + i + aa[i]; append(l, r), append(r, l); } long long ans = 0; for (int i = 0; i < n * 3; i++) { for (int oi = eo[i]; oi--; ) { int j = ej[i][oi]; used[j] = 1; } for (int oi = eo[i]; oi--; ) { int j = ej[i][oi]; if (eo[i] > eo[j] || eo[i] == eo[j] && i < j) for (int oj = eo[j]; oj--; ) { int k = ej[j][oj]; if (used[k]) ans++; } } for (int oi = eo[i]; oi--; ) { int j = ej[i][oi]; used[j] = 0; } } for (int i = 0; i < n * 3; i++) free(ej[i]); return ans / 3; } long long count_triples(vi aa) { int n = aa.size(); long long ans = 0; for (int i = 0; i < n; i++) { int j, k = i + aa[i]; if (k < n && aa[k] < aa[i]) { j = k - aa[k]; if (j > i && aa[j] == j - i) ans++; if (aa[k] * 2 != aa[i]) { j = i + aa[k]; if (j < k && aa[j] == k - j) ans++; } } } for (int k = 0; k < n; k++) { int i = k - aa[k], j; if (i >= 0 && aa[i] < aa[k]) { j = i + aa[i]; if (j < k && aa[j] == k - j) ans++; if (aa[i] * 2 != aa[k]) { j = k - aa[i]; if (j > i && aa[j] == j - i) ans++; } } } for (int i = 0; i < n; i++) { int j = i + aa[i]; if (j < n && aa[j] > aa[i] && aa[j] != aa[i] * 2) { int k = i + aa[j]; if (k < n && aa[k] == k - j) ans++; } } ans += count_triangles(aa, n); return ans; } vi 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...