P7475 - Go Running

内存限制：128 MB 时间限制：5 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：9 通过：6

Zhang3 is the class leader. Recently she's implementing a policy about long-distance running. This forces every student in her class to take a run.

There is a main road in the school from west to east, which can be regarded as an infinite axis, and its positive direction is east. Positions on the road are represented with numbers. In order to complete the task, each student must run along the main road. Each student can decide the following things:

- The time to start running.
- The time to finish running.
- The position to start running.
- The direction of running, which is either west or east.

Once these things are decided, the student will appear at the starting position on the road at the start time, then start running in the chosen direction at a speed of

1m/s. The student disappears at the finish time. Each student will only run once.

Zhang3 knows that some students are not following her policy, so she set up some monitors. According to technical issues, the monitors can only report that there's at least one student at a certain place at a certain time. Finally Zhang3 received

n reports.

Help Zhang3 determine the minimum possible number of students who have run.

The first line of the input gives the number of test cases,

T(1≤T≤100).

Ttest cases follow.
For each test case, the first line contains an integer

n(1≤n≤105), the number of reports.
Then

nlines follow, the

ithof which contains two integers

ti,xi(1≤ti,xi≤109), representing that there's at least one student at position

xi(m)at time

ti(s).
The sum of

nin all test cases doesn't exceed

5×105.

For each test case, print a line with an integer, representing the minimum number of students who have run.

2
1

2020 Multi-University Training Contest 4

7475: Go Running

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签