| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 241 | 122 | 100 | 49.505% |
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번