Codeforces

Number of Segments that Contain Each Other

I really did not know how to go about solving this problem.

Ran into this while doing a practice problem: https://codeforces.com/contest/1915/problem/F

You can brute force it in $O(n^2)$, but I had no idea on how to do it faster.

• I had some ideas of storing the start and end points, and somehow iterating through that

We can iterate over the segments in increasing order of the 𝑏 position and for each of them adding the number of segments that we have already passed that have an $a$ value larger than the one of the current segment.

• Yea, like I actually had many of the ideas, but couldn’t find a solution

Go through b in ascending order, and keep track of how many ‘a’s are in the set, which are greater than the current a!!

• That was actually very much my initial idea

So something like this, but the problem is that std::distance can do O(n) worst case

• You want to do something like it - s.begin(), however that doesn’t work with a set

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        int b[n];
        vector<pair<int, int>> v;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            cin >> b[i];
            v.push_back({b[i], a[i]});
        }
        sort(v.begin(), v.end());
        set<int> s;
        int total = 0;
        for (int i = 0; i < n; i++) {
            auto it = s.upper_bound(v[i].second);
            total += i - distance(s.begin(), it); // This works for edge case because s.begin() == s.end() when it's empty
            s.insert(v[i].second);
        }
        cout << total << endl;
    }
 
    return 0;
}