Universal Cup Judging System

Universal Cup

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

Velkomin í TV Time hjá Mr. Ant Tenna! Í þessari umferð leiksins færðu $n$ fötur, þar sem $i$-ta fatan hefur hámarksrúmmál upp á $v_i$ rúmmálseiningar af vatni. Í upphafi leiksins verða allar föturnar fylltar alveg af vatni og verkefni þitt er að halda eins miklu vatni og þú getur í þeim næstu $t$ sekúndurnar. En hér kemur fléttan: þessar fötur eru bilaðar! $i$-ta fatan er með lekahraða $l_i$, sem þýðir að á hverri sekúndu eftir að leikurinn hefst leka $l_i$ rúmmálseiningar af vatni úr $i$-tu fötunni.

Áður en leikurinn hefst máttu sameina hvaða fjölda af fötum sem er í eina. Fatan sem verður til hefur rúmmál sem jafngildir mesta rúmmálinu meðal sameinuðu fatanna og lekahraða sem jafngildir minnsta lekahraðanum meðal sameinuðu fatanna. Þú getur framkvæmt sameiningar eins oft og þú vilt, en þær verða að fara fram áður en vatni er hellt í.

Tenna leggur fram $q$ spurningar, þar sem $i$-ta spurningin hefur tímamörk $t_i$. Fyrir hvert $1 \le i \le q$ skaltu reikna mesta mögulega heildarrúmmál vatns sem eftir er eftir $t_i$ sekúndur. Athugaðu að hver spurning er óháð hinum.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 5 \times 10^4$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 2 \times 10^5$), sem gefur til kynna fjölda fata.

Önnur línan inniheldur $n$ heiltölur $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), þar sem $v_i$ er rúmmál $i$-tu fötunnar.

Þriðja línan inniheldur $n$ heiltölur $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), þar sem $l_i$ er lekahraði $i$-tu fötunnar.

Fjórða línan inniheldur heiltölu $q$ ($1 \le q \le 2 \times 10^5$), sem gefur til kynna fjölda spurninga.

Fimmta línan inniheldur $q$ heiltölur $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), þar sem $t_i$ eru tímamörkin fyrir $i$-tu fyrirspurnina.

Það er tryggt að hvorki summa $n$ né summa $q$ yfir öll prófunartilvik fari yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $q$ heiltölur aðskildar með bili, þar sem $i$-ta heiltalan er mesta mögulega heildarrúmmál sem eftir er eftir $t_i$ sekúndur.

Dæmi

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.