Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓
İstatistikler

Selamat datang di TV Time bersama Mr. Ant Tenna! Pada babak permainan ini, Anda diberikan $n$ ember, dengan ember ke-$i$ memiliki kapasitas maksimum sebesar $v_i$ satuan volume air. Pada awal permainan, semua ember akan diisi penuh dengan air, dan misi Anda adalah mempertahankan air sebanyak mungkin selama $t$ detik berikutnya. Namun ada kejutannya: ember-ember ini bocor! Ember ke-$i$ memiliki laju kebocoran sebesar $l_i$, yang berarti setiap detik setelah permainan dimulai, ember ke-$i$ meneteskan $l_i$ satuan volume air.

Sebelum permainan dimulai, Anda boleh menggabungkan sejumlah ember berapa pun menjadi satu. Ember hasil penggabungan memiliki kapasitas yang sama dengan kapasitas maksimum di antara ember-ember yang digabungkan, serta laju kebocoran yang sama dengan laju kebocoran minimum di antara ember-ember yang digabungkan. Anda dapat melakukan penggabungan sebanyak berapa kali pun, tetapi semuanya harus dilakukan sebelum mengisi air.

Tenna mengajukan $q$ pertanyaan, dengan pertanyaan ke-$i$ memiliki batas waktu $t_i$. Untuk setiap $1 \le i \le q$, hitung total volume maksimum air yang tersisa setelah $t_i$ detik. Perhatikan bahwa setiap pertanyaan bersifat independen.

Masukan

Terdapat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 5 \times 10^4$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 2 \times 10^5$), yang menyatakan banyaknya ember.

Baris kedua berisi $n$ bilangan bulat $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), dengan $v_i$ adalah kapasitas ember ke-$i$.

Baris ketiga berisi $n$ bilangan bulat $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), dengan $l_i$ adalah laju kebocoran ember ke-$i$.

Baris keempat berisi sebuah bilangan bulat $q$ ($1 \le q \le 2 \times 10^5$), yang menyatakan banyaknya pertanyaan.

Baris kelima berisi $q$ bilangan bulat $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), dengan $t_i$ adalah batas waktu untuk kueri ke-$i$.

Dijamin bahwa baik jumlah $n$ maupun jumlah $q$ di semua kasus uji tidak akan melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $q$ bilangan bulat yang dipisahkan oleh spasi, dengan bilangan bulat ke-$i$ adalah total volume maksimum air yang tersisa setelah $t_i$ detik.

Contoh

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.