Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Tervetuloa Mr. Ant Tennan TV Time -ohjelmaan! Tällä pelikierroksella sinulle annetaan $n$ ämpäriä, joista $i$:nnen ämpärin enimmäistilavuus on $v_i$ tilavuusyksikköä vettä. Pelin alussa kaikki ämpärit täytetään piripintaan vedellä, ja tehtäväsi on pitää mahdollisimman paljon vettä talletettuna seuraavien $t$ sekunnin ajan. Mutta tässä on juonenkäänne: nämä ämpärit ovat rikki! $i$:nnellä ämpärillä on vuotonopeus $l_i$, mikä tarkoittaa, että joka sekunti pelin alkamisen jälkeen $i$:nnestä ämpäristä valuu pois $l_i$ tilavuusyksikköä vettä.

Ennen pelin alkua voit yhdistää minkä tahansa määrän ämpäreitä yhdeksi. Tuloksena syntyvän ämpärin tilavuus on yhtä suuri kuin yhdistettyjen ämpäreiden suurin tilavuus, ja sen vuotonopeus on yhtä suuri kuin yhdistettyjen ämpäreiden pienin vuotonopeus. Voit tehdä yhdistämisiä mielivaltaisen monta kertaa, mutta ne on suoritettava ennen veden täyttämistä.

Tenna esittää $q$ kysymystä, joista $i$:nnellä kysymyksellä on aikaraja $t_i$. Laske jokaiselle $1 \le i \le q$ suurin mahdollinen jäljellä oleva kokonaistilavuus $t_i$ sekunnin kuluttua. Huomaa, että jokainen kysymys on riippumaton muista.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 5 \times 10^4$), joka ilmaisee testitapausten määrän. Jokaisessa testitapauksessa:

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2 \times 10^5$), joka ilmaisee ämpäreiden määrän.

Toinen rivi sisältää $n$ kokonaislukua $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), missä $v_i$ on $i$:nnen ämpärin tilavuus.

Kolmas rivi sisältää $n$ kokonaislukua $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), missä $l_i$ on $i$:nnen ämpärin vuotonopeus.

Neljäs rivi sisältää kokonaisluvun $q$ ($1 \le q \le 2 \times 10^5$), joka ilmaisee kysymysten määrän.

Viides rivi sisältää $q$ kokonaislukua $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), missä $t_i$ on $i$:nnen kyselyn aikaraja.

On taattu, että lukujen $n$ summa eikä lukujen $q$ summa yli kaikkien testitapausten ylitä arvoa $2 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää $q$ välilyönnillä erotettua kokonaislukua, missä $i$:s kokonaisluku on suurin mahdollinen jäljellä oleva kokonaistilavuus $t_i$ sekunnin kuluttua.

Esimerkit

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.