ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 I: 校门外的树（大）

内存限制：128 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：318 通过：87
返回比赛提交提交记录

题目描述

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入格式

输入文件的第一行有两个整数L（1 <= L <= 1e9）和 M（1 <= M <= 100000），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出格式

输出文件t包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

输入样例 复制 

500 3
150 300
100 200
470 471

输出样例 复制 

298

数据范围与提示

对于20%的数据，区域之间没有重合的部分；
 对于其它的数据，区域之间有重合的情况。


10000 100
6193 8245
3840 9103
7702 8392
3654 6843
201 734
3199 4667
1591 4597
5149 7292
2455 3071
2799 4940
2777 4759
2581 9083
346 1340
96 5282
1514 6036
2387 5080
762 8841
1717 2074
2584 8739
3976 9620
141 3131
611 5498
2711 6318
33 2121
5496 9943
8162 8516
1303 9580
8019 9634
677 1435
999 6744
5906 7146
3329 4091
1320 2958
8281 9485
685 4181
921 7878
1365 2925
4786 7101
252 3362
1201 3520
5668 9786
3946 6183
6162 9372
875 1026
7406 8478
6199 7330
111 6627
2938 4628
3726 8788
457 8443
290 2395
392 3310
2284 5349
4832 8133
5833 7712
62 8141
8103 9040
3074 3756
2129 9863
1548 3989
7078 8921
727 2874
634 6410
2506 9811
2418 7845
2468 4253
2191 2636
4480 9816
3813 4608
2356 8045
796 5435
1535 5607
7316 8597
2237 2967
1036 2516
908 4100
665 7091
717 2413
973 4401
1181 8745
792 4248
6261 9002
1573 2582
401 1042
2551 7181
286 2305
1659 6561
4864 5371
5850 7598
849 8409
610 9435
6672 7047
3628 6961
1295 7569
4284 7229
250 9038
4170 6803
1962 7785
2558 3877
3537 8830
90

分类标签