| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 213 | 113 | 91 | 51.705% |
Yan Hao has $n$ swords numbered from 1ドル$ to $n$. Sword $i$ has attack $a[i]$ and defence $b[i]$.
Yan Hao thinks that sword $i$ is useless if there exists a different sword $j$ ($j \ne i$) such that $a[i] ≤ a[j]$ and $b[i] ≤ b[j]$. That is, a sword $i$ is useless if the attack and defence of another sword $j$ are both at least as good as that of sword $i$. If a sword is not useless, we say that it is useful.
Two swords are considered equivalent if they have the same attack and same defence. It is guaranteed that no pair of swords are equivalent.
Help Yan Hao find the number of useful swords in his collection.
The first line of input contains exactly 1ドル$ integer, $n$.
The next $n$ lines of input contains two space-separated integers each. The $i$-th such line of input will contain $a[i]$ and $b[i]$ respectively, indicating the attack and defence of sword $i$.
The output should contain one integer, the number of useful swords.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | $n ≤ 500$ |
| 2 | 21 | $a[i], b[i] ≤ 500$ |
| 3 | 34 | $a[i] = i$ |
| 4 | 25 | $a[i] \ne a[j]$ for every 1ドル ≤ i < j ≤ n$ |
| 5 | 9 | No additional constraints |
3 2 3 1 3 5 3
1
Comparing sword 1ドル$ with sword 3ドル,ドル we have $a[1] = 2 ≤ 5 = a[3]$ and $b[1] = 3 ≤ 3 = b[3],ドル so sword 1ドル$ is useless.
Comparing sword 2ドル$ with sword 1ドル,ドル we have $a[2] = 1 ≤ 2 = a[1]$ and $b[2] = 3 ≤ 3 = b[1],ドル so sword 2ドル$ is useless.
Sword 3ドル$ is the only useful sword.
4 5 6 2 5 6 9 1 3
1
Olympiad > National Olympiad in Informatics (Singapore) > Qualification > NOI 2023 Qualification 2번