CF1131B.Draw!

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You still have partial information about the score during the historic football match. You are given a set of pairs (ai,bi)(a_i, b_i), indicating that at some point during the match the score was "aia_i: bib_i". It is known that if the current score is «xx:yy», then after the goal it will change to "x+1x+1:yy" or "xx:y+1y+1". What is the largest number of times a draw could appear on the scoreboard?

The pairs "aia_i:bib_i" are given in chronological order (time increases), but you are given score only for some moments of time. The last pair corresponds to the end of the match.

你仍然掌握着这场历史性足球比赛的部分比分信息。给你一组数对 (ai,bi)(a_i, b_i),表示在比赛的某个时刻比分曾为 "aia_i: bib_i"。已知:若当前比分为 «xx:yy»,则进一球后比分将变为 "x+1x+1:yy" 或 "xx:y+1y+1"。请问记分牌上最多可能出现多少次平局(即 x=yx = y 的时刻)?

这些数对 "aia_i:bib_i" 按时间顺序给出(时间递增),但你仅获知了部分时刻的比分。最后一组数对对应比赛结束时的比分。

输入格式

The first line contains a single integer nn (1≤n≤100001 \le n \le 10000) — the number of known moments in the match.

Each of the next nn lines contains integers aia_i and bib_i (0≤ai,bi≤1090 \le a_i, b_i \le 10^9), denoting the score of the match at that moment (that is, the number of goals by the first team and the number of goals by the second team).

All moments are given in chronological order, that is, sequences xix_i and yjy_j are non-decreasing. The last score denotes the final result of the match.

第一行包含一个整数 nn(1≤n≤100001 \le n \le 10000)—— 表示比赛中已知时刻的数量。

接下来的 nn 行每行包含两个整数 aia_i 和 bib_i(0≤ai,bi≤1090 \le a_i, b_i \le 10^9),表示该时刻的比赛比分(即第一支队伍的进球数和第二支队伍的进球数)。

所有时刻按时间顺序给出,即序列 aia_i 和 bib_i 均为非递减序列。最后一个比分表示比赛的最终结果。

输出格式

Print the maximum number of moments of time, during which the score was a draw. The starting moment of the match (with a score 0:0) is also counted.

输出比分平局的最多时刻数量。比赛开始时刻(比分为 0:0)也计入在内。

输入输出样例

  • 输入#1

    3
    2 0
    3 1
    3 4

    输出#1

    2
  • 输入#2

    3
    0 0
    0 0
    0 0

    输出#2

    1
  • 输入#3

    1
    5 4

    输出#3

    5

说明/提示

In the example one of the possible score sequences leading to the maximum number of draws is as follows: 0:0, 1:0, 2:0, 2:1, 3:1, 3:2, 3:3, 3:4.

在该示例中,一种能达成最多平局场次的可能比分序列如下:0:0,1:0,2:0,2:1,3:1,3:2,3:3,3:4。

输入解题思路,AI测评打分。不知道怎么写?

首页