Submission #1262798

#TimeUsernameProblemLanguageResultExecution timeMemory
1262798Canuc80kTriple Peaks (IOI25_triples)C++20
4.57 / 100
13 ms1856 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(); int T = max(1, (int)std::sqrt((double)n)); using ll = long long; // posA[v] = các chỉ số i có a[i] = v (tăng dần) unordered_map<int, vector<int>> posA; posA.reserve(n * 2); for (int i = 0; i < n; ++i) posA[a[i]].push_back(i); // posPair[(x,y)] = các chỉ số j có (a[j]=x, b[j]=y) (tăng dần) auto pack = [](int x, int y) -> uint64_t { return ( (uint64_t)(uint32_t)x << 32 ) | (uint32_t)y; }; unordered_map<uint64_t, vector<int>> posPair; posPair.reserve(n * 2); for (int i = 0; i < n; ++i) posPair[pack(a[i], b[i])].push_back(i); // Đánh dấu heavy theo bậc của a=y vector<int> heavyY; heavyY.reserve(posA.size()); unordered_set<int> isHeavy; isHeavy.reserve(posA.size() * 2); for (auto &p : posA) { if ((int)p.second.size() > T) { heavyY.push_back(p.first); isHeavy.insert(p.first); } } ll ans = 0; // ----- LIGHT: xử lý theo k, mỗi lần duyệt ≤ T chỉ số i và đếm j bằng binary search for (int k = 0; k < n; ++k) { int x = a[k], y = b[k]; auto itY = posA.find(y); if (itY == posA.end()) continue; if (isHeavy.find(y) != isHeavy.end()) continue; // y nặng sẽ xử lý ở phần HEAVY const auto &Iy = itY->second; // các i có a[i] = y for (int t = 0; t < (int)Iy.size() && Iy[t] < k; ++t) { int i = Iy[t]; uint64_t key = pack(x, b[i]); auto itPair = posPair.find(key); if (itPair == posPair.end()) continue; const auto &vec = itPair->second; // chỉ số j có (a[j]=x, b[j]=b[i]) // Đếm j trong (i, k): i < j < k 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); } } // ----- HEAVY: quét toàn mảng cho từng y nặng for (int y : heavyY) { // cntI[t] = số i đã thấy (i < hiện tại) với a[i]=y và b[i]=t unordered_map<int, int> cntI; cntI.reserve(T * 4); // P[x] = số cặp (i, j) đã tạo với i có a[i]=y, b[i]=b[j], j có a[j]=x (và i<j) unordered_map<int, long long> P; P.reserve(T * 8); for (int t = 0; t < n; ++t) { // 1) k = t (b[k] = y): cộng số cặp (i, j) có j < k, i < j if (b[t] == y) { auto itP = P.find(a[t]); if (itP != P.end()) ans += itP->second; } // 2) j = t: tạo cặp (i, j) với mọi i trước đó thỏa a[i]=y, b[i]=b[j] P[a[t]] += (long long)cntI[b[t]]; // 3) i = t: thêm i vào kho với a[i]=y if (a[t] == y) cntI[b[t]]++; } } return ans; } long long count_triples(std::vector<int> H) { } std::vector<int> construct_range(int M, int K) { return {1,3,1,1,2,1,4,3,2,3,1,1,2,3,4,1,2,1,3,3}; }

Compilation message (stderr)

triples.cpp: In function 'long long int count_triples(std::vector<int>)':
triples.cpp:97:1: warning: no return statement in function returning non-void [-Wreturn-type]
   97 | }
      | ^
#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...