/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君は初めての車を購入するため、中古車販売店を訪れました。販売店には N 台の中古車があり、それぞれについて「価格」と「走行距離」が分かっています。i 番目の車の価格は P_i 万円、走行距離は K_i km です。
高橋君は予算の都合上、価格が高すぎる車は購入できません。一方で、安すぎる車は品質に不安があるため避けたいとも考えています。さらに、走行距離が長すぎる車は故障のリスクが高いため避けたいと考えています。
具体的には、高橋君は以下の条件をすべて満たす車を「候補車」と呼ぶことにします：
- 価格が L 万円以上 R 万円以下である（すなわち L \leq P_i \leq R）
- 走行距離が M km 以下である（すなわち K_i \leq M）
N 台の中古車のうち「候補車」に該当するものの台数を求めてください。各車は 1 台ずつ区別して数えるものとします。
制約
- 1 \leq N \leq 10^5
- 1 \leq L \leq R \leq 10^4
- 1 \leq M \leq 10^6
- 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
- 1 \leq K_i \leq 10^6 (1 \leq i \leq N)
- 入力はすべて整数である
入力
N L R M P_1 K_1 P_2 K_2 \vdots P_N K_N
- 1 行目には、中古車の台数 N、価格の下限 L、価格の上限 R、走行距離の上限 M がスペース区切りで与えられる。
- 続く N 行のうち i 行目 (1 \leq i \leq N) には、i 番目の車の価格 P_i と走行距離 K_i がスペース区切りで与えられる。
出力
「候補車」の台数を 1 行で出力せよ。
入力例 1
5 100 200 50000 150 30000 250 20000 80 10000 200 50000 180 60000
出力例 1
2
入力例 2
4 150 300 40000 100 30000 500 20000 200 80000 50 50000
出力例 2
0
入力例 3
10 50 150 100000 120 80000 50 100000 200 50000 30 90000 150 100001 75 60000 100 120000 90 99999 160 30000 45 100000
出力例 3
4
入力例 4
20 200 500 80000 300 50000 150 40000 450 80000 500 80001 200 79999 600 30000 250 90000 350 70000 199 60000 501 50000 400 80000 210 1 180 10000 320 75000 275 100000 480 60000 200 80000 100 20000 500 50000 300 80000
出力例 4
11
入力例 5
1 1 1 1 1 1
出力例 5
1
Score : 233 pts
Problem Statement
Takahashi is visiting a used car dealership to purchase his first car. The dealership has N used cars, and for each car, the "price" and "mileage" are known. The i-th car has a price of P_i ten-thousand yen and a mileage of K_i km.
Due to budget constraints, Takahashi cannot purchase a car that is too expensive. On the other hand, he also wants to avoid cars that are too cheap, as he is concerned about their quality. Furthermore, he wants to avoid cars with too high a mileage due to the increased risk of breakdowns.
Specifically, Takahashi defines a car as a "candidate car" if it satisfies all of the following conditions:
- The price is at least L ten-thousand yen and at most R ten-thousand yen (i.e., L \leq P_i \leq R)
- The mileage is at most M km (i.e., K_i \leq M)
Among the N used cars, find the number of cars that qualify as "candidate cars." Each car is counted individually.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq L \leq R \leq 10^4
- 1 \leq M \leq 10^6
- 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
- 1 \leq K_i \leq 10^6 (1 \leq i \leq N)
- All inputs are integers
Input
N L R M P_1 K_1 P_2 K_2 \vdots P_N K_N
- The first line contains the number of used cars N, the lower bound of price L, the upper bound of price R, and the upper bound of mileage M, separated by spaces.
- Each of the following N lines, where the i-th line (1 \leq i \leq N), contains the price P_i and mileage K_i of the i-th car, separated by spaces.
Output
Output the number of "candidate cars" in a single line.
Sample Input 1
5 100 200 50000 150 30000 250 20000 80 10000 200 50000 180 60000
Sample Output 1
2
Sample Input 2
4 150 300 40000 100 30000 500 20000 200 80000 50 50000
Sample Output 2
0
Sample Input 3
10 50 150 100000 120 80000 50 100000 200 50000 30 90000 150 100001 75 60000 100 120000 90 99999 160 30000 45 100000
Sample Output 3
4
Sample Input 4
20 200 500 80000 300 50000 150 40000 450 80000 500 80001 200 79999 600 30000 250 90000 350 70000 199 60000 501 50000 400 80000 210 1 180 10000 320 75000 275 100000 480 60000 200 80000 100 20000 500 50000 300 80000
Sample Output 4
11
Sample Input 5
1 1 1 1 1 1
Sample Output 5
1