Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Velkommen til Mr. Ant Tennas TV Time! I denne runden av spillet får du $n$ bøtter, der den $i$-te bøtten har en maksimal kapasitet på $v_i$ volumenheter vann. Ved starten av spillet fylles alle bøttene helt opp med vann, og oppdraget ditt er å holde på så mye vann som mulig i løpet av de neste $t$ sekundene. Men her er tvisten: disse bøttene er ødelagte! Den $i$-te bøtten har en lekkasjehastighet på $l_i$, som betyr at hvert sekund etter at spillet starter, lekker det ut $l_i$ volumenheter vann fra den $i$-te bøtten.

Før spillet starter, kan du slå sammen et hvilket som helst antall bøtter til én. Den resulterende bøtten får en kapasitet lik den største kapasiteten blant de sammenslåtte bøttene, og en lekkasjehastighet lik den minste lekkasjehastigheten blant de sammenslåtte bøttene. Du kan utføre sammenslåinger så mange ganger du vil, men de må gjøres før det fylles i vann.

Tenna stiller $q$ spørsmål, der det $i$-te spørsmålet har en tidsgrense $t_i$. For hver $1 \le i \le q$, beregn det maksimale totale gjenværende volumet etter $t_i$ sekunder. Merk at hvert spørsmål er uavhengig.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 5 \times 10^4$) som angir antall testtilfeller. For hvert testtilfelle:

Den første linjen inneholder et heltall $n$ ($1 \le n \le 2 \times 10^5$), som angir antall bøtter.

Den andre linjen inneholder $n$ heltall $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), der $v_i$ er kapasiteten til den $i$-te bøtten.

Den tredje linjen inneholder $n$ heltall $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), der $l_i$ er lekkasjehastigheten til den $i$-te bøtten.

Den fjerde linjen inneholder et heltall $q$ ($1 \le q \le 2 \times 10^5$), som angir antall spørsmål.

Den femte linjen inneholder $q$ heltall $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), der $t_i$ er tidsgrensen for den $i$-te spørringen.

Det er garantert at verken summen av $n$ eller summen av $q$ over alle testtilfeller vil overstige $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én linje som inneholder $q$ heltall atskilt med mellomrom, der det $i$-te heltallet er det maksimale totale gjenværende volumet etter $t_i$ sekunder.

Eksempler

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.