主页
题目
状态
排名
OI排名
统计
题解
请登录
常用链接
AOJ考试平台
老赵的Gitee代码
编译原理模拟考试平台
Java技术手册
FCC网站
菜鸟网
在线工具箱
字节豆包GPT
代码可视化
力扣网
牛客网
洛谷
杭电OJ
CodeForce
隐藏编译器
Problem D: 地铁(subway)
上一题
正确率: $0.00\%$
下一题
Time Limit
$1$ 秒/Second(s)
Memory Limit
$128$ 兆字节/Megabyte(s)
提交总数
$0$
正确数量
$0$
"
裁判形式
标准裁判/Standard Judge
我的状态
尚未尝试
难度
分类标签
×
为本题添加算法分类(请不要超过5个)
当前分类(单击移除):
单击选择分类:
Description
<div> <span style="font-size:16px;">B 市的地铁历史悠久,小雪和小可可乘坐的 X 号线是环形路线,上面分布着 n 个车站,</span> </div> <div> <span style="font-size:16px;">相</span><span style="font-size:16px;">邻</span><span style="font-size:16px;">两</span><span style="font-size:16px;">个</span><span style="font-size:16px;">车</span><span style="font-size:16px;">站</span><span style="font-size:16px;">之</span><span style="font-size:16px;">间</span><span style="font-size:16px;">的</span><span style="font-size:16px;">铁</span><span style="font-size:16px;">路</span><span style="font-size:16px;">长</span><span style="font-size:16px;">度</span><span style="font-size:16px;">为</span><span style="font-size:16px;">正</span><span style="font-size:16px;">整</span><span style="font-size:16px;">数</span><span style="font-size:16px;">。现在小雪进行了一些观察,得到了 m 条信息,第 i 条信</span><span style="font-size:16px;">息是如下形式之一:</span> </div> <div> <span style="font-size:16px;">1.</span><span style="font-size:16px;">环上顺时针由 Si</span><span style="font-size:16px;">到 Ti</span><span style="font-size:16px;">的一段距离不小于一个给定的值 Li(Si 和 Ti</span><span style="font-size:16px;">是两个车站);</span> </div> <div> <span style="font-size:16px;">2.</span><span style="font-size:16px;">环上顺时针由 Si</span><span style="font-size:16px;">到 Ti</span><span style="font-size:16px;">的一段距离不大于一个给定的值 Li。</span> </div> <div> <span style="font-size:16px;">小雪想要你计算最后 X 线地铁的总长度有多少种不同的合法取值。</span> </div>
Input
<div> <span style="font-size:16px;">第一行两个空格隔开的正整数 n 和 m。</span> </div> <div> <span style="font-size:16px;">下面 m 行,第 i 行四个空格隔开的正整数 typei , Si , Ti , Li,其中 typei</span><span style="font-size:16px;">∈ {1, 2} 表示信息的</span><span style="font-size:16px;">类型。车站顺时针编号为从 1 开始的连续整数。保证 1 ≤ Si , Ti ≤ n 且 Si</span><span style="font-size:16px;">= Ti。</span> </div>
Output
<p> <span style="font-size:16px;">仅一行一个整数,表示所求答案。如果有无穷种取值,请输出 -1。</span> </p> <p> <span style="font-size:16px;">保证答案不为0,即至少有一种可能的方案。</span> </p>
Sample Input
复制
4 6 1 1 3 3 2 2 4 5 1 2 4 4 1 3 1 4 2 4 2 5 1 4 2 3
Sample Output
复制
4
提示
<div> <span style="font-size:16px;">【样例解释】</span> </div> <div> <span style="font-size:16px;">定义数组 d[1..4],其中 d[i] 表示 i 号车站顺时针到 i + 1</span> </div> <div> <span style="font-size:16px;">号车站的铁路长度。</span> </div> <div> <span style="font-size:16px;">1.</span><span style="font-size:16px;">d = [1, 2, 2, 2],总长度为 7;</span> </div> <div> <span style="font-size:16px;">2.</span><span style="font-size:16px;">d = [1, 2, 2, 3],总长度为 8;</span> </div> <div> <span style="font-size:16px;">3.</span><span style="font-size:16px;">d = [1, 2, 2, 4],总长度为 9;</span> </div> <div> <span style="font-size:16px;">4.</span><span style="font-size:16px;">d = [1, 2, 3, 4],总长度为 10。</span> </div> <div> <span style="font-size:16px;">可以证明,不存在其他的可能长度,于是答案为 4。</span> </div>
AOJ
Please Login