We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Triple sum
  2. Discussions

Triple sum

  • urossevkusic
     + 0 comments

    My algorithm works as follows:: 1. remove duplicates from all vectors (generate sets, then recreate vectors); note that the vectors are now sorted because std::set is an ordered collection 2. for all elements q in B, find the number of elements r in C such that q <= r using binary search, and store the results in vector. Also, generate a prefix sum of that vector starting from its end. 3. for all elements p in A, find the first element q in B such that p <= q. Simply add all triplets with q' >= q in B, that are now stored in the prefix sum array of B.

    long long triplets(vector<int> a, vector<int> b, vector<int> c) {
    std::set<int> ta(a.begin(), a.end());
    std::set<int> tb(b.begin(), b.end());
    std::set<int> tc(c.begin(), c.end());
    std::vector<long long> A(ta.begin(), ta.end()), B(tb.begin(), tb.end()), C(tc.begin(), tc.end());
    long long count = 0;
    std::vector<long long> pref(B.size());
    pref[B.size() - 1] = std::distance(C.begin(), std::upper_bound(C.begin(), C.end(), B[B.size() - 1]));
    for(int i = B.size() - 2; i >= 0; --i) {
        auto it = std::upper_bound(C.begin(), C.end(), B[i]);
        pref[i] = pref[i + 1] + std::distance(C.begin(), it);
    }
    
    for(int p : A) {
        auto it = std::lower_bound(B.begin(), B.end(), p);
        if(it == B.end()) continue;
        else count += pref[std::distance(B.begin(), it)];
    }
    return count;
}