SP23536 FRONT - Front

题目描述

小佩塔尔和小尼古拉伊正在玩一款策略战争游戏,两人争夺对方基地的控制权。两人的基地分别位于地图的对角线两端(小尼古拉伊的基地在左下角,佩塔尔的基地在右上角)。游戏中,双方可以使用在地图上的士兵进行攻击或防御,士兵的位置由坐标 $(x,y)$ 表示。 在某个关键时刻,佩塔尔透过小尼古拉伊的屏幕,记下了所有敌方士兵的位置,并确保这些位置是按 $x$ 坐标升序排列的。为了制定有效的攻击计划,他需要知道有多少小尼古拉伊的士兵处于最易受攻击的状态,即位于“前线”。 如果没有其他士兵可以“覆盖”士兵 $V(x, y)$,即不存在其他士兵 $V'(x', y')$ 使得 $x \leq x'$ 且 $y \leq y'$,那么士兵 $V(x, y)$ 就被认为是**在前线**上的。

输入格式

第一行输入一个自然数 $N$,表示小尼古拉伊的士兵数量。接下来的 $N$ 行,每行包含两个整数 $x_i$ 和 $y_i$,分别表示第 $i$ 个士兵在地图上的坐标。士兵按 $x$ 坐标升序排列。

输出格式

输出一行,包含一个整数 $F$,表示小尼古拉伊位于前线的士兵数量。

说明/提示

- $1 \leq N \leq 10^5$ - $1 \leq x_i, y_i \leq 10^9$ 这题要求我们找出在给定条件下,没有被“右上方”其他士兵覆盖的士兵数量。 **本翻译由 AI 自动生成**