Hossam and Friends (Codeforces 1771B)
Tags: Others, two pointers

Hossam makes a big party, and he will invite his friends to the party.He has $$$n$$$ friends numbered from $$$1$$$ to $$$n$$$. They will be arranged in a queue as follows: $$$1, 2, 3, \ldots, n$$$.Hossam has a list of $$$m$$$ pairs of his friends that don't know each other. Any pair not present in this list are friends.A subsegment of the queue starting from the friend $$$a$$$ and ending at the friend $$$b$$$ is $$$[a, a + 1, a + 2, \ldots, b]$$$. A subsegment of the queue is called good when all pairs of that segment are friends.Hossam wants to know how many pairs $$$(a, b)$$$ there are ($$$1 \le a \le b \le n$$$), such that the subsegment starting from the friend $$$a$$$ and ending at the friend $$$b$$$ is good.

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$), the number of test cases. Description of the test cases follows.The first line of each test case contains two integer numbers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$) representing the number of friends and the number of pairs, respectively.The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i\le n$$$, $$$x_i \neq y_i$$$) representing a pair of Hossam's friends that don't know each other.Note that pairs can be repeated.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print an integer — the number of good subsegments.

Note: In the first example, the answer is $$$4$$$.The good subsegments are:[1][2][3][1, 2]In the second example, the answer is $$$5$$$.The good subsegments are:[1][2][3][4][3, 4]

Sample Inputs:
2
3 2
1 3
2 3
4 2
1 2
2 3

Sample Outputs:
4
5

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter

def s():
    (n, m) = map(int, input().split())
    l = (n + 1) * [100001]
    for b in range(m):
        p = sorted([int(i) for i in input().split()])
        (mi, ma) = (p[0], p[1])
        l[mi] = min(l[mi], ma - mi)
    l[-1] = 1
    for i in range(n - 1, 0, -1):
        c = l[i + 1] + 1
        l[i] = min(c, l[i])
    s = str(sum(l[1:]))
    return s + '\n'
res = ''
t = int(input())
for x in range(t):
    res += s()
print(res)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter

def s():
    (n, m) = map(int, input().split())
    l = (n + 1) * [100001]
    for b in range(m):
        p = sorted([int(i) for i in input().split()])
        (mi, ma) = (p[0], p[1])
        l[mi] = min(l[mi], ma - mi)
    l[-1] = 1
    for i in range(n - 1, 0, -1):
        c = l[i + 1] + 1
        l[i] = min(c, l[i])
    print(sum(l[1:]))
t = int(input())
for x in range(t):
    s()

Solution (Python):
from collections import defaultdict
from collections import Counter
import sys
input = sys.stdin.readline

def read_list_integers():
    return list(map(int, input().split(' ')))

def print_str_line(str):
    sys.stdout.write(str + '\n')

def print_number(number):
    print_str_line(f'{number}')

def ans(number_of_persons, pairs):
    ans = 0
    pairs.sort(key=lambda pair: pair[1])
    prev_invalid_index = 0
    last_not_counted_index = 0
    for pair in pairs:
        if prev_invalid_index < pair[0]:
            ans += (pair[1] - last_not_counted_index) * (last_not_counted_index - prev_invalid_index + pair[1] - 1 - prev_invalid_index) // 2
            prev_invalid_index = pair[0]
            last_not_counted_index = pair[1]
    ans += (number_of_persons - last_not_counted_index + 1) * (last_not_counted_index - prev_invalid_index + number_of_persons - prev_invalid_index) // 2
    return ans

def get_decreasing_pair(pair):
    if pair[0] > pair[1]:
        return pair[::-1]
    return pair
number_of_test_cases = int(input())
for i in range(number_of_test_cases):
    (number_of_persons, number_of_pairs) = read_list_integers()
    pairs = [get_decreasing_pair(read_list_integers()) for j in range(number_of_pairs)]
    _ans = ans(number_of_persons, pairs)
    print_number(_ans)