Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 難易度: [表示] ハック可能 ✓
統計

Mr. Ant Tenna の TV タイムへようこそ!このラウンドのゲームでは $n$ 個のバケツが与えられ、$i$ 番目のバケツには最大で $v_i$ の体積の水を入れることができます。ゲーム開始時にすべてのバケツは水で満杯にされ、あなたの使命は次の $t$ 秒間でできるだけ多くの水をバケツの中に残すことです。しかし、ここで厄介な点があります。これらのバケツは壊れているのです!$i$ 番目のバケツの漏水速度は $l_i$ であり、ゲーム開始後 1 秒ごとに $i$ 番目のバケツから $l_i$ の体積の水が漏れ出します。

ゲーム開始前に、任意の個数のバケツを 1 つに統合することができます。統合後のバケツの容量は統合したバケツの最大容量に等しくなり、漏水速度は統合したバケツの最小漏水速度に等しくなります。統合は任意の回数行うことができますが、すべて水を入れる前に行わなければなりません。

Tenna は $q$ 個の質問を出します。$i$ 番目の質問には制限時間 $t_i$ があります。各 $1 \le i \le q$ について、$t_i$ 秒後に残っている水の総体積の最大値を求めてください。なお、各質問は独立です。

入力

複数のテストケースが与えられます。入力の 1 行目にはテストケースの個数を表す整数 $T$($1 \le T \le 5 \times 10^4$)が与えられます。各テストケースについて:

1 行目にはバケツの個数を表す整数 $n$($1 \le n \le 2 \times 10^5$)が与えられます。

2 行目には $n$ 個の整数 $v_1, v_2, \cdots, v_n$($1 \le v_i \le 4 \times 10^{13}$)が与えられます。ここで $v_i$ は $i$ 番目のバケツの容量です。

3 行目には $n$ 個の整数 $l_1, l_2, \cdots, l_n$($0 \le l_i \le 10^9$)が与えられます。ここで $l_i$ は $i$ 番目のバケツの漏水速度です。

4 行目には質問の個数を表す整数 $q$($1 \le q \le 2 \times 10^5$)が与えられます。

5 行目には $q$ 個の整数 $t_1, t_2, \cdots, t_q$($0 \le t_i \le 10^9$)が与えられます。ここで $t_i$ は $i$ 番目のクエリの制限時間です。

すべてのテストケースにおける $n$ の総和および $q$ の総和はいずれも $2 \times 10^5$ を超えないことが保証されます。

出力

各テストケースについて、空白で区切られた $q$ 個の整数を 1 行に出力してください。ここで $i$ 番目の整数は $t_i$ 秒後に残っている水の総体積の最大値です。

入出力例

2
4
5 4 7 6
2 1 3 2
3
3 1 2
4
19 47 21 13
5 14 2 3
5
5 2 6 1 4
4 14 8
43 67 38 77 48

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.