Competitive Programming Solutions

abc143_d - Triangles

24 Dec 2020 — Tags: sorting,binary_search — URL

If we have the length of the sticks, $l$, sorted non-decreasingly, we can count all possible triangles by listing two sides $a$, and $b$ and finding the position, $c$, where the length starts to become degenerate.

Remember that $a + b > c$ and $a \leq b \leq c$.

This can be done with binary search or two-pointers.

Time complexity: $O(n \log{n})$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi l(n);
    for (auto &li : l)
        cin >> li;
    sort(begin(l), end(l));
    int ans = 0;
    for (int i = 0; i < n - 2; ++i)
    {
        for (int j = i + 1; j < n - 1; ++j)
        {
            auto it = lower_bound(begin(l) + j + 1, end(l), l[i] + l[j]);
            int k = distance(begin(l), it);
            if (k - 1 > j)
                ans += k - j - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Related posts