[NOISG 2023 Qualification] Swords

Luogu
IDLGP10728
Time1000ms
Memory1024MB
DifficultyP2
数学贪心2023排序扫描线NOISG(新加坡)
YH 有 $n$ 把剑,第 $i$ 把剑的攻击力为 $a_i$,防御能力为 $b_i$。 对于一把剑 $i$,如果存在一个 $j(j \not = i)$,使得 $a_i\le a_j$ 且 $b_i\le b_j$,那么 YH 就认为这把剑是无用的。反之,他就认为这把剑是有用的。 在本题中,我们保证,不可能找到两把剑 $i,j$,使得 $a_i=a_j$ 且 $b_i=b_j$。 请你帮助 YH 求出这 $n$ 把剑中,有用的剑的数量。 ## Input 第一行,一个整数 $n$。 接下来 $n$ 行,每行两个整数 $a_i,b_i$,表示第 $i$ 把剑形的攻击力和防御能力。 ## Output 一个整数,表示有用的剑**的数量**。 [samples] ## Note |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$1$|$11$|$n\le500$| |$2$|$21$|$a_i,b_i\le500$| |$3$|$34$|$a_i=i$| |$4$|$25$|对于每一个 $1\le i<j\le n$,有 $a_i\not =a_j$| |$5$|$9$|无| 对于所有数据,$1\le n\le100000,1\le a_i,b_i\le10^9$。
Samples
Input #1
3
2 3
1 3
5 3
Output #1
1
Input #2
4
5 6
2 5
6 9
1 3
Output #2
1
API Response (JSON)
{
  "problem": {
    "name": "[NOISG 2023 Qualification] Swords",
    "description": {
      "content": "YH 有 $n$ 把剑,第 $i$ 把剑的攻击力为 $a_i$,防御能力为 $b_i$。 对于一把剑 $i$,如果存在一个 $j(j \\not = i)$,使得 $a_i\\le a_j$ 且 $b_i\\le b_j$,那么 YH 就认为这把剑是无用的。反之,他就认为这把剑是有用的。 在本题中,我们保证,不可能找到两把剑 $i,j$,使得 $a_i=a_j$ 且 $b_i=b_j$。 请你帮助",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10728"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "YH 有 $n$ 把剑,第 $i$ 把剑的攻击力为 $a_i$,防御能力为 $b_i$。\n\n对于一把剑 $i$,如果存在一个 $j(j \\not = i)$,使得 $a_i\\le a_j$ 且 $b_i\\le b_j$,那么 YH 就认为这把剑是无用的。反之,他就认为这把剑是有用的。\n\n在本题中,我们保证,不可能找到两把剑 $i,j$,使得 $a_i=a_j$ 且 $b_i=b_j$。\n\n请你帮助...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments