Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

Benvenuti al TV Time di Mr. Ant Tenna! In questo round del gioco ti vengono dati $n$ secchi, dove l'$i$-esimo secchio ha una capacità massima di $v_i$ volumi d'acqua. All'inizio del gioco tutti i secchi verranno riempiti completamente d'acqua, e la tua missione è trattenerne il più possibile per i successivi $t$ secondi. Ma ecco il colpo di scena: questi secchi sono bucati! L'$i$-esimo secchio ha una velocità di perdita pari a $l_i$, il che significa che ogni secondo dopo l'inizio del gioco l'$i$-esimo secchio perde $l_i$ volumi d'acqua.

Prima che il gioco inizi, puoi fondere un numero qualsiasi di secchi in uno solo. Il secchio risultante ha una capacità uguale alla capacità massima tra i secchi fusi e una velocità di perdita uguale alla velocità di perdita minima tra i secchi fusi. Puoi effettuare fusioni un numero arbitrario di volte, ma devono essere eseguite prima di versare qualsiasi quantità d'acqua.

Tenna pone $q$ domande, dove l'$i$-esima domanda ha un limite di tempo $t_i$. Per ogni $1 \le i \le q$, calcola il massimo volume totale trattenuto dopo $t_i$ secondi. Nota che ogni domanda è indipendente.

Dati di ingresso

Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 5 \times 10^4$) che indica il numero di casi di test. Per ciascun caso di test:

La prima riga contiene un intero $n$ ($1 \le n \le 2 \times 10^5$), che indica il numero di secchi.

La seconda riga contiene $n$ interi $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), dove $v_i$ è la capacità dell'$i$-esimo secchio.

La terza riga contiene $n$ interi $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), dove $l_i$ è la velocità di perdita dell'$i$-esimo secchio.

La quarta riga contiene un intero $q$ ($1 \le q \le 2 \times 10^5$), che indica il numero di domande.

La quinta riga contiene $q$ interi $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), dove $t_i$ è il limite di tempo per l'$i$-esima query.

È garantito che né la somma di $n$ né la somma di $q$ su tutti i casi di test supererà $2 \times 10^5$.

Dati di uscita

Per ciascun caso di test, stampa una riga contenente $q$ interi separati da uno spazio, dove l'$i$-esimo intero è il massimo volume totale trattenuto dopo $t_i$ secondi.

Esempi

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.