Universal Cup Judging System

Universal Cup

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

Мистер Ант Теннаның «TV Time» шоуына қош келдіңіз! Ойынның бұл раундында сізге $n$ шелек беріледі, мұндағы $i$-ші шелектің ең үлкен сыйымдылығы $v_i$ су көлеміне тең. Ойын басталғанда барлық шелектер суға толық толтырылады, ал сіздің міндетіңіз — келесі $t$ секунд ішінде мүмкіндігінше көп суды сақтап қалу. Бірақ бір гәп бар: бұл шелектер тесік! $i$-ші шелектің су ағу жылдамдығы $l_i$, яғни ойын басталғаннан кейін әр секунд сайын $i$-ші шелектен $l_i$ көлем су ағып кетеді.

Ойын басталғанға дейін кез келген сандағы шелекті біріктіріп, бір шелек жасай аласыз. Пайда болған шелектің сыйымдылығы біріктірілген шелектердің ішіндегі ең үлкен сыйымдылыққа тең болады, ал су ағу жылдамдығы біріктірілген шелектердің ішіндегі ең кіші су ағу жылдамдығына тең болады. Біріктіруді қалағаныңызша көп рет жасай аласыз, бірақ олардың барлығы су құймас бұрын орындалуы керек.

Тенна $q$ сұрақ қояды, мұндағы $i$-ші сұрақтың уақыт шегі — $t_i$. Әрбір $1 \le i \le q$ үшін $t_i$ секундтан кейін сақталып қалатын судың ең үлкен жалпы көлемін есептеңіз. Әрбір сұрақ бір-біріне тәуелсіз екенін ескеріңіз.

Кіріс деректер

Бірнеше тест жиынтығы берілген. Кіріс деректердің бірінші жолында тест жиынтықтарының санын білдіретін $T$ ($1 \le T \le 5 \times 10^4$) бүтін саны берілген. Әрбір тест жиынтығы үшін:

Бірінші жолда шелектер санын білдіретін $n$ ($1 \le n \le 2 \times 10^5$) бүтін саны берілген.

Екінші жолда $n$ бүтін сан $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$) берілген, мұндағы $v_i$ — $i$-ші шелектің сыйымдылығы.

Үшінші жолда $n$ бүтін сан $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$) берілген, мұндағы $l_i$ — $i$-ші шелектің су ағу жылдамдығы.

Төртінші жолда сұрақтар санын білдіретін $q$ ($1 \le q \le 2 \times 10^5$) бүтін саны берілген.

Бесінші жолда $q$ бүтін сан $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$) берілген, мұндағы $t_i$ — $i$-ші сұранымның уақыт шегі.

Барлық тест жиынтықтары бойынша $n$ қосындысы да, $q$ қосындысы да $2 \times 10^5$ мәнінен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиынтығы үшін бос орынмен бөлінген $q$ бүтін саннан тұратын бір жол шығарыңыз, мұндағы $i$-ші бүтін сан — $t_i$ секундтан кейінгі сақталған ең үлкен жалпы су көлемі.

Мысалдар

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.