Exam in MAC (Codeforces 1935D)
Tags: Math, combinatorics

The Master's Assistance Center has announced an entrance exam, which consists of the following.The candidate is given a set $$$s$$$ of size $$$n$$$ and some strange integer $$$c$$$. For this set, it is needed to calculate the number of pairs of integers $$$(x, y)$$$ such that $$$0 \leq x \leq y \leq c$$$, $$$x + y$$$ is not contained in the set $$$s$$$, and also $$$y - x$$$ is not contained in the set $$$s$$$.Your friend wants to enter the Center. Help him pass the exam!

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$c$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq c \leq 10^9$$$) — the size of the set and the strange integer.The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_{n}$$$ ($$$0 \leq s_1 < s_2 < \ldots < s_{n} \leq c$$$) — the elements of the set $$$s$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, output a single integer — the number of suitable pairs of integers.

Note: In the first test case, the following pairs are suitable: $$$(0, 0)$$$, $$$(2, 2)$$$, $$$(3, 3)$$$.In the third test case, the following pairs are suitable: $$$(0, 1)$$$, $$$(0, 2)$$$, $$$(0, 4)$$$, $$$(1, 3)$$$, $$$(2, 6)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, $$$(4, 5)$$$, $$$(4, 6)$$$, $$$(5, 6)$$$.

Sample Inputs:
8
3 3
1 2 3
1 179
57
4 6
0 3 5 6
1 1
1
5 10
0 2 4 8 10
5 10
1 3 5 7 9
4 10
2 4 6 7
3 1000000000
228 1337 998244353

Sample Outputs:
3
16139
10
2
33
36
35
499999998999122959

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

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

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, c) = readInts()
    s = readList()
    cnt = ans = 0
    for i in range(n):
        cnt += s[i] % 2
        ans += (s[i] + 1) // 2
    ans += (c + 1) * (c + 2) // 2 - n * (c + 2) + (cnt * (cnt + 1) // 2 + (n - cnt) * (n - cnt + 1) // 2)
    return ans
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
for _ in range(t):
    (n, c) = map(int, input().split())
    s = list(map(int, input().split()))
    ans0 = (c + 1) * (c + 2) // 2
    cnt = [0] * 2
    for i in s:
        ans0 -= c - i + 1 + (i + 2) // 2
        cnt[i & 1] += 1
    for i in cnt:
        ans0 += i * (i + 1) // 2
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from collections import *
from heapq import *
import sys
from os import path

def input():
    return sys.stdin.readline().strip()

def input_int():
    return int(input())

def input_list(delimiter=' '):
    return list(map(int, input().split(delimiter)))

def input_string():
    return input()

def solve():
    (n, c) = input_list()
    nums = input_list()
    invalid_pairs = 0
    total_pairs = (c + 1) * (c + 2) // 2
    counts = [0, 0]
    for num in nums:
        L = num // 2 + 1 - counts[num & 1]
        R = c - num
        invalid_pairs += L + R
        counts[num & 1] += 1
    print(total_pairs - invalid_pairs)

def main():
    testcases = input_int()
    for _ in range(testcases):
        solve()
if __name__ == '__main__':
    if path.exists('input.txt'):
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    main()