以下是来自日本的原始新闻PDF,已完整保存和染色。



可复制的 PDF 提取文本
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Examination
試験(Examination)
N 人の学生が数学と情報の2 科目からなる試験を受けた.i 人目(1 ≦i ≦N) の学生は,数学でS i 点,情
報でTi 点を取った.T 教授とI 教授は,これらの学生を,試験の結果によって合格と不合格に振り分けよ
うとしている.
• T 教授は,数学と情報のいずれの科目も重要だと考えており,数学でA 点以上,かつ,情報でB 点以
上取った学生を合格させたいと思っている.
• I 教授は,合計点のみを重視しており,数学と情報の合計でC 点以上取った学生を合格させたいと
思っている.
• 2 人の教授いずれも合格させたいと思っている学生のみが合格となる.
あなたは,これらの合格基準A, B,C の値を知らない.代わりに,Q 通りの3 つの整数の組(Xj, Yj, Zj)
(1 ≦j ≦Q) それぞれについて,A = Xj, B = Yj, C = Z j であったときに合格する学生の人数を知りたい.
学生の人数,各学生の成績,いくつかの合格基準が与えられたとき,それぞれの合格基準について合格す
る学生の人数を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.
N Q
S 1 T1
...
S N TN
X1 Y1 Z1
...
XQ YQ ZQ
出力
出力はQ 行からなる.j 行目(1 ≦j ≦Q) には,A = Xj, B = Yj, C = Z j であったときに合格する学生の人
数を出力せよ.
試験– 1 / 3
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Examination
制約
• 1 ≦N ≦100 000.
• 1 ≦Q ≦100 000.
• 0 ≦S i ≦1 000 000 000 (1 ≦i ≦N).
• 0 ≦Ti ≦1 000 000 000 (1 ≦i ≦N).
• 0 ≦X j ≦1 000 000 000 (1 ≦j ≦Q).
• 0 ≦Y j ≦1 000 000 000 (1 ≦j ≦Q).
• 0 ≦Z j ≦2 000 000 000 (1 ≦j ≦Q).
小課題
1. (2 点) N ≦3 000,Q ≦3 000.
2. (20 点) S i ≦100 000, Ti ≦100 000 (1 ≦i ≦N),Xj ≦100 000, Yj ≦100 000, Zj = 0 (1 ≦j ≦Q).
3. (21 点) S i ≦100 000, Ti ≦100 000 (1 ≦i ≦N),Xj ≦100 000, Yj ≦100 000, Zj ≦200 000 (1 ≦j ≦Q).
4. (57 点) 追加の制約はない.
入出力例
入力例1 出力例1
5 4 2
35 100 4
70 70 1
45 15 1
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
• A = 20, B = 50, C = 120 のとき,1 人目および2 人目の学生のみが数学で20 点以上,情報で50 点
以上,合計で120 点以上を取っているので,合格する学生は2 人である.
試験– 2 / 3
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Examination
• A = 10, B = 10, C = 100 のとき,1 人目,2 人目,4 人目,5 人目の学生のみが数学で10 点以上,
情報で10 点以上,合計で100 点以上を取っているので,合格する学生は4 人である.
• A = 60, B = 60, C = 80 のとき,2 人目の学生のみが数学で60 点以上,情報で60 点以上,合計で80
点以上を取っているので,合格する学生は1 人である.
• A = 0, B = 100, C = 100 のとき,1 人目の学生のみが数学で0 点以上,情報で100 点以上,合計で
100 点以上を取っているので,合格する学生は1 人である.
入力例2 出力例2
10 10 1
41304 98327 3
91921 28251 5
85635 59191 8
30361 72671 8
28949 96958 3
99041 37826 3
10245 2726 3
19387 20282 5
60366 87723 6
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117
試験– 3 / 3