2384 . 小祥愛騎車

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

fatman
:truck:

User's AC Ratio

20.0% (2/10)

Submission's AC Ratio

4.1% (2/49)

Tags

CKcon 2024-CKcon

Description

小祥從 F1 退役之後決定轉戰摩托車比賽，加入 MotoGP。MotoGP 是由施巨砲 (GP) 舉辦的摩托車賽事，每場比賽都有許多人參加，但是因為小祥跟施巨砲太強了，所以今年度的 MotoGP 儼然成為了小祥跟施巨砲的一對一對決。

MotoGP 中，有 N 個可選的比賽賽道，從左到右為第 1 個到第 N 個。小祥跟施巨砲各自熟悉不同的賽道，因此對於第 i 個賽道來說，小祥的技能值為 Ai，施巨砲的技能值為 Bi。在一場 MotoGP 的賽事中，會選取一段區間 [i,j] ，並用第 i 個到第 j 個賽道進行比賽。對於小祥來說，他想要讓他與施巨砲的技能值差距越大；同時，因為他覺得他的體力比施巨砲好（每多一場比賽，他就比施巨砲好 K 個單位的體能），他也想要讓比賽的賽道數量越多越好。因此，對於一段區間 [i,j] 來說，小祥對它的好感度為 maxi≤v≤jAv−maxi≤v≤jBv+K∗(j−i+1)。

接下來會舉行連續 Q 天的賽事，每天只有第 L 到第 R 條賽道是能比賽的，比賽委員會會在這些賽道內選擇一段連續的區間 [i,j] 比賽 (L≤i≤j≤R)。小祥靠著關係賄賂了比賽委員會，讓他可以選擇要選哪些賽道比賽。請幫他寫一個程式，計算對於每天的比賽，他的最大好感度為何（注意好感度可能為負數）。

Input Format

第一行有兩個整數 N,K，意義如題目所述
第二行有 N 個正整數 A1,…,AN，代表小祥對賽道的技能值
第三行有 N 個正整數 B1,…,BN，代表施巨砲對賽道的技能值
第四行有一個正整數 Q ，代表詢問數量
接下來的 Q 行中，每行有兩個正整數 Li,Ri ，代表當天有比賽的賽道

對於所有測試資料：

  • 1≤N,Q≤100000
  • 0≤K≤108
  • 1≤Ai,Bi≤1013

Output Format

請輸出 Q 行，每行輸出一個整數，代表第 i 天的最大好感度。

Sample Input 1

5 2
8 4 5 3 9
2 6 1 2 10
4
1 5
1 3
2 3
4 5

Sample Output 1

10
8
6
3

Sample Input 2

10 5
88 16 42 15 94 65 3 9 98 4
50 3 95 36 25 59 35 77 1 69
6
1 10
5 9
2 4
5 10
9 10
2 10

Sample Output 2

102
102
18
102
102
102

Hints

範例測資 1 解釋：

對於第 1 天，小祥可以選擇 [1,4]，此時好感度為 8−6+2⋅(4−1+1)=10。
對於第 2 天，小祥可以選擇 [1,3]，此時好感度為 8−6+2⋅(3−1+1)=8。
對於第 3 天，小祥可以選擇 [3,3]，此時好感度為 5−1+2⋅(3−3+1)=6。
對於第 4 天，小祥可以選擇 [4,4]，此時好感度為 3−2+2⋅(4−4+1)=3。

Problem Source

2024 MotoGP 系列賽可以在 YouTube SPOTV Asia 免費收看喔～

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~6 N,Q≤100 7
3 0~11 N≤2000 14
4 3, 8, 12~17 K=0 15
5 18~26 Q=1、L1=1、R1=N 26
6 0~40 無特別限制 38

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4500 1048576 65536 1 2 3 6
1 4500 1048576 65536 1 2 3 6
2 4500 1048576 65536 2 3 6
3 4500 1048576 65536 2 3 4 6
4 4500 1048576 65536 2 3 6
5 4500 1048576 65536 2 3 6
6 4500 1048576 65536 2 3 6
7 4500 1048576 65536 3 6
8 4500 1048576 65536 3 4 6
9 4500 1048576 65536 3 6
10 4500 1048576 65536 3 6
11 4500 1048576 65536 3 6
12 4500 1048576 65536 4 6
13 4500 1048576 65536 4 6
14 4500 1048576 65536 4 6
15 4500 1048576 65536 4 6
16 4500 1048576 65536 4 6
17 4500 1048576 65536 4 6
18 4500 1048576 65536 5 6
19 4500 1048576 65536 5 6
20 4500 1048576 65536 5 6
21 4500 1048576 65536 5 6
22 4500 1048576 65536 5 6
23 4500 1048576 65536 5 6
24 4500 1048576 65536 5 6
25 4500 1048576 65536 5 6
26 4500 1048576 65536 5 6
27 4500 1048576 65536 6
28 4500 1048576 65536 6
29 4500 1048576 65536 6
30 4500 1048576 65536 6
31 4500 1048576 65536 6
32 4500 1048576 65536 6
33 4500 1048576 65536 6
34 4500 1048576 65536 6
35 4500 1048576 65536 6
36 4500 1048576 65536 6
37 4500 1048576 65536 6
38 4500 1048576 65536 6
39 4500 1048576 65536 6
40 4500 1048576 65536 6
Submit
Back to Top