Codeforces Round 932 (Div. 2) |
---|
Закончено |
Центр Помощи Магистрам объявил вступительный экзамен, который заключается в следующем.
Кандидату даётся множество $$$s$$$ размера $$$n$$$, а также некоторое странное число $$$c$$$. Для этого множества нужно посчитать количество пар целых чисел $$$(x, y)$$$ таких, что $$$0 \leq x \leq y \leq c$$$, $$$x + y$$$ не содержится в множестве $$$s$$$, а также $$$y - x$$$ не содержится в множестве $$$s$$$.
Ваш друг хочет поступить в Центр. Помогите ему сдать экзамен!
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$c$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq c \leq 10^9$$$) — размер множества и странное число.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_{n}$$$ ($$$0 \leq s_1 < s_2 < \ldots < s_{n} \leq c$$$) — элементы множества $$$s$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество подходящих пар целых чисел.
83 31 2 31 179574 60 3 5 61 115 100 2 4 8 105 101 3 5 7 94 102 4 6 73 1000000000228 1337 998244353
3 16139 10 2 33 36 35 499999998999122959
В первом наборе входных данных подходят следующие пары: $$$(0, 0)$$$, $$$(2, 2)$$$, $$$(3, 3)$$$.
В третьем наборе входных данных подходят следующие пары: $$$(0, 1)$$$, $$$(0, 2)$$$, $$$(0, 4)$$$, $$$(1, 3)$$$, $$$(2, 6)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, $$$(4, 5)$$$, $$$(4, 6)$$$, $$$(5, 6)$$$.
Название |
---|