Submission #1262809

#TimeUsernameProblemLanguageResultExecution timeMemory
1262809Canuc80kTriple Peaks (IOI25_triples)C++20
0 / 100
21 ms12212 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; ll res = 0; void add(ll i, ll j, ll k) { // cout << "Debug: " << i << ' ' << j << ' ' << k << endl; res ++; } long long countr(const vector<int> &a, const vector<int> &b) { int n = (int)a.size(); if (n == 0) return 0; int T = max(1, (int)std::sqrt((double)n)); vector<vector<int>> posA(n); for (int i = 0; i < n; ++i) posA[a[i]].push_back(i); vector<tuple<int,int,int>> triples; triples.reserve(n); for (int i = 0; i < n; ++i) triples.emplace_back(a[i], b[i], i); sort(triples.begin(), triples.end(), [](auto &L, auto &R){ if (get<0>(L) != get<0>(R)) return get<0>(L) < get<0>(R); return get<1>(L) < get<1>(R); }); vector<vector<pair<int, vector<int>>>> posPairByA(n); for (int idx = 0; idx < (int)triples.size(); ) { int x = get<0>(triples[idx]); int y = get<1>(triples[idx]); vector<int> indices; while (idx < (int)triples.size() && get<0>(triples[idx]) == x && get<1>(triples[idx]) == y) { indices.push_back(get<2>(triples[idx])); ++idx; } posPairByA[x].emplace_back(y, std::move(indices)); } vector<int> heavyY; vector<char> isHeavy(n, 0); for (int v = 0; v < n; ++v) { if ((int)posA[v].size() > T) { heavyY.push_back(v); isHeavy[v] = 1; } } ll ans = 0; auto get_pair_vec = [&posPairByA](int x, int y) -> const vector<int>* { const auto &vec = posPairByA[x]; auto it = std::lower_bound(vec.begin(), vec.end(), y, [](const pair<int, vector<int>> &p, int val){ return p.first < val; }); if (it != vec.end() && it->first == y) return &it->second; return nullptr; }; for (int k = 0; k < n; ++k) { int x = a[k], y = b[k]; const auto &Iy = posA[y]; if (Iy.empty()) continue; if (isHeavy[y]) continue; for (int t = 0; t < (int)Iy.size() && Iy[t] < k; ++t) { int i = Iy[t]; const vector<int> *vec = get_pair_vec(x, b[i]); if (!vec) continue; int L = int(upper_bound(vec->begin(), vec->end(), i) - vec->begin()); int R = int(lower_bound(vec->begin(), vec->end(), k) - vec->begin()); ans += (ll)(R - L); } } vector<int> cntI(n, 0); vector<ll> P(n, 0); vector<int> touchedCnt; touchedCnt.reserve(n); vector<int> touchedP; touchedP.reserve(n); for (int y : heavyY) { touchedCnt.clear(); touchedP.clear(); for (int t = 0; t < n; ++t) { if (b[t] == y) { ans += P[a[t]]; } if (cntI[b[t]] != 0) { if (P[a[t]] == 0) touchedP.push_back(a[t]); P[a[t]] += (ll)cntI[b[t]]; } if (a[t] == y) { if (cntI[b[t]] == 0) touchedCnt.push_back(b[t]); cntI[b[t]]++; } } for (int v : touchedCnt) cntI[v] = 0; for (int v : touchedP) P[v] = 0; } return ans; } long long count_triples(std::vector<int> H) { res = 0; // #TH: a[k] max for (int k = 2; k < H.size(); k ++) { int i = k - H[k]; if (i < 0 || H[i] >= H[k]) continue; int j1 = k - H[i], j2 = i + H[i]; if (j1 < 0 || H[j1] >= H[k] || H[j1] != j1 - i) j1 = -1; if (j2 >= k || H[j2] >= H[k] || H[j2] != k - j2) j2 = -1; if (j1 != -1) add(i, j1, k); if (j2 != -1 && j1 != j2) add(i, j2, k); } // #TH: a[i] max for (int i = 0; i + 2 < H.size(); i ++) { int k = i + H[i]; if (k >= H.size() || H[k] >= H[i]) continue; int j1 = k - H[k], j2 = i + H[k]; if (j1 < 0 || H[j1] >= H[i] || H[j1] != j1 - i) j1 = -1; if (j2 >= k || H[j2] >= H[i] || H[j2] != k - j2) j2 = -1; if (j1 != -1) add(i, j1, k); if (j2 != -1 && j1 != j2) add(i, j2, k); } // #TH: a[j] max, j - i = a[i] for (int i = 0; i + 2 < H.size(); i ++) { int j = i + H[i]; if (j >= H.size() || H[j] <= H[i]) continue; int k = i + H[j]; if (k >= H.size() || H[k] >= H[j] || k - H[k] != j || k - j == H[i]) k = -1; if (k != -1) add(i, j, k); } // #TH: a[j] max, j - i = a[k] // for (int i = 0; i + 2 < H.size(); i ++) { // for (int k = i + H[i] + 1; k < H.size(); k ++) { // int j = i + H[k]; if (j != k - H[i] || j >= H.size()) continue; // if (H[i] >= H[j] || H[j] <= H[k] || k - i != H[j] || j >= k) continue; // // cout << "OKE: " << i << ' ' << j << ' ' << k << endl; // add(i, j, k); // } // } vector<int> a, b; for (int i = 0; i < H.size(); i ++) a.push_back(H[i] + i); for (int i = 0; i < H.size(); i ++) b.push_back(i - H[i]); // for (int i = 0; i < a.size(); i ++) // for (int j = i + 1; j < a.size(); j ++) // for (int k = j + 1; k < a.size(); k ++) // if (a[i] == b[k] && a[j] == a[k] && b[i] == b[j]) res ++; res += countr(a, b); return res; } int rand(int l, int r) { static random_device rd; static mt19937 gen(rd()); uniform_int_distribution<int> dist(l, r); return dist(gen); } std::vector<int> construct_range(int M, int K) { vector<int> save; ll attempt = 1e7 / M, val = -1; while (attempt --) { vector<int> res; for (int i = 0; i < M; i ++) res.push_back(rand(1, sqrt(M))); ll x = count_triples(res); if (x > val) {val = x; save = res;} } return save; // return {4,3,2,3,1,1,2,3,3,1,2,1,4,3,2,3,1,1,2,3}; }
#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...