#P18383. Ring of Beads
Ring of Beads
Ring of Beads
题目描述
有 颗珠子按顺时针方向排成一圈,编号为 。每颗珠子可以被染成青色或白色。
对任意 ,定义顺时针闭区间 :
- 若 ,包含编号 的珠子。
- 若 ,包含编号 的珠子。
用 表示 内青色珠子的数量。
现在给出 条限制,每条限制由四元组 表示:
- :要求 。
- :要求 。
- :要求 。
首先判断是否存在满足全部限制的染色方案。若存在,求有多少个区间 的青色珠子数在所有合法染色方案中都相同。不同区间的固定数值不需要相同。
两个区间 与 不同,当且仅当 或 。特别地,虽然
都包含整个圆环,它们仍然是 个不同区间。共有 个待统计的有序端点区间。
输入格式
第一行包含两个整数 (,)。
接下来 行,每行包含四个整数 ,其中 ,,, 为该区间内珠子的数量。
本题输入只有一组数据。
输出格式
若不存在合法染色方案,输出一行一个整数 。
否则输出一行一个整数,表示青色珠子数在所有合法染色中保持不变的区间数量。
样例输入 1
16 8
1 1 3 1
1 5 7 1
1 9 11 1
1 13 15 1
2 2 6 1
2 6 10 1
2 10 14 1
2 14 2 1
样例输出 1
128
样例输入 2
1000000000 1
2 114514 114513 0
样例输出 2
1000000000000000000
样例输入 3
100 3
3 1 10 1
3 91 100 1
3 81 20 2
样例输出 3
253
样例输入 4
6 3
1 1 3 2
1 4 6 2
2 2 5 1
样例输出 4
-1
样例说明
第一组样例只有两种合法染色,C 表示青色,W 表示白色:
CWWWCWWWCWWWCWWW
WWCWWWCWWWCWWWCW
恰好有 个区间中的一半,即 个区间,在两种染色中包含相同数量的青色珠子。
第二组样例中的区间覆盖整个圆环,限制要求没有青色珠子,因此唯一合法染色是全部为白色;所有 个区间都应计入答案。