124 . 堆疊遊戲 EX

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

75.0% (3/4)

Tags

ioicamp ioicamp-2023

Description

大家有看過今年 NPSC 初賽時高中組的堆疊遊戲嗎？如果你沒看過的話，現在讓你看看。

edison 只要看到網路上的手遊廣告就會載下來試玩看看，堆疊遊戲也不例外。堆疊遊戲的規則非常簡單，那就是玩家會拿到若干個裝著一堆整數的堆疊，並且持有一個計數器從初始值 0 開始，每次挑選一個堆疊將其頂端的數字拿出來加進計數器內，只要能夠完整將所有數字拿出來，並滿足過程中計數器的值都非負，就算是完成一個關卡。

喜歡自我挑戰的 edison 覺得這款遊戲似乎有些容易，因此他決定給自己加上一個條件：遊戲過程計數器值出現過的最大值必須最小。

在這個限制下，遊戲似乎就無法簡單的在 edison 腦海內模擬了，因此他希望能夠事先知道這個「最小的最大值」可以多小，好讓自己能夠知道有沒有因為自己訂下的規則輸掉。

由於這個問題難度有點高，因此 edison 請你先幫忙處理兩個堆疊的情況就好，舉例而言，假設兩個堆疊的大小分別是 3 和 4，並且第一個堆疊內的整數由上到下依序是 [3,1,−4]，第二個堆疊內的整數由上到下依序是 [1,−5,9,2]，edison 可以照著「一一二二二一二」的順序依序從對應的堆疊拿出數字加進計數器內，這樣會滿足計數器的數字依序為「3,4,5,0,9,5,7」，過程都非負，過程的最大值是 9；當然，edison 也可以照著「一一二二二二一」的順序拿數字，但這樣計數器的數字依序會為「3,4,5,0,9,11,7」，儘管過程非負，但過程的最大值是 11，並不符合 edison 給自己的限制。

請你撰寫一支程式在讀入兩個堆疊內的整數後，輸出計數器初始值從 0 開始後完整將所有數字拿出來的過程中，在滿足計數器的數值總是非負的情況下，過程最大值最小可以是多小。

比賽結束之後，雖然你如願解出了這個問題，但是你開始思考，如果我們想特別詢問從兩個堆疊的一種指定狀態取數字到另一種指定狀態中，這個過程計數器的最大值最小可以是多小，有沒有什麼迅速的演算法呢？

正式地說，你會有 Q 個好奇的詢問，其中第 i 次的詢問會有四個數字 pi,qi,ri,si，代表現在：

  • 目前第一個堆疊已經拿出了 pi 個數字。
  • 目前第二個堆疊已經拿出了 qi 個數字。
  • 經過一系列拿數字出來的操作後，第一個堆疊含已經拿出的數字，總共會拿出 ri 個數字。
  • 經過一系列拿數字出來的操作後，第二個堆疊含已經拿出的數字，總共會拿出 si 個數字。
  • 包括一開始和結尾，你希望得知這期間拿出數字的過程中，同樣在滿足計數器的數值總是非負的情況下，計數器的最大值最小可以是多小。

注意到你不在乎「第一個堆疊和第二個堆疊分別拿出 pi 和 qi 個數字」這個狀態可能無法從最一開始達到，你只在乎自此狀態開始後的過程必須讓計數器的數值總是非負（包含該狀態的當下）。

為了滿足你自己的好奇心，解答你自己的問題吧。

Input Format

輸入第一行有三個正整數 N,M,Q，依序代表第一個和第二個堆疊的整數數量以及你好奇的詢問數量。

接著兩行，首行是一個長度為 N 的整數序列 a1,a2,…,aN，代表第一個堆疊由上數下來的第 i 個整數是 ai；次行是一個長度為 M 的整數序列 b1,b2,…,bM，代表第二個堆疊由上數下來的第 i 個整數是 bi。

接著 Q 行，第 i 行會有四個非負整數 pi,qi,ri,si，代表你希望得知從分別拿了 pi,qi 個數字一路到 ri,si 個數字的答案。

  • 1≤N,M≤500
  • −106≤ai,bi≤106
  • 1≤Q≤8×104
  • 0≤pi≤ri≤N
  • 0≤qi≤si≤N

Output Format

輸出 Q 行，第 i 行代表第 i 個詢問的答案，若從狀態 pi,qi 到狀態 ri,si 不可能讓計數器的數值總是非負，輸出 −1 以表示這個過程不合法。

Sample Input 1

3 4 1
3 1 -4
1 -5 9 2
0 0 3 4

Sample Output 1

9

Sample Input 2

3 4 5
3 1 -4
1 -5 9 2
0 0 3 4
0 0 0 3
2 0 2 2
0 3 1 4
2 0 3 1

Sample Output 2

9
-1
5
10
4

Hints

Problem Source

IOICamp 2023 Day4 pG

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0, 2~37 Q=1。 20
3 0~68 無特別限制。 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 524288 65536 1 2 3
1 4000 524288 65536 1 3
2 4000 524288 65536 2 3
3 4000 524288 65536 2 3
4 4000 524288 65536 2 3
5 4000 524288 65536 2 3
6 4000 524288 65536 2 3
7 4000 524288 65536 2 3
8 4000 524288 65536 2 3
9 4000 524288 65536 2 3
10 4000 524288 65536 2 3
11 4000 524288 65536 2 3
12 4000 524288 65536 2 3
13 4000 524288 65536 2 3
14 4000 524288 65536 2 3
15 4000 524288 65536 2 3
16 4000 524288 65536 2 3
17 4000 524288 65536 2 3
18 4000 524288 65536 2 3
19 4000 524288 65536 2 3
20 4000 524288 65536 2 3
21 4000 524288 65536 2 3
22 4000 524288 65536 2 3
23 4000 524288 65536 2 3
24 4000 524288 65536 2 3
25 4000 524288 65536 2 3
26 4000 524288 65536 2 3
27 4000 524288 65536 2 3
28 4000 524288 65536 2 3
29 4000 524288 65536 2 3
30 4000 524288 65536 2 3
31 4000 524288 65536 2 3
32 4000 524288 65536 2 3
33 4000 524288 65536 2 3
34 4000 524288 65536 2 3
35 4000 524288 65536 2 3
36 4000 524288 65536 2 3
37 4000 524288 65536 2 3
38 4000 524288 65536 3
39 4000 524288 65536 3
40 4000 524288 65536 3
41 4000 524288 65536 3
42 4000 524288 65536 3
43 4000 524288 65536 3
44 4000 524288 65536 3
45 4000 524288 65536 3
46 4000 524288 65536 3
47 4000 524288 65536 3
48 4000 524288 65536 3
49 4000 524288 65536 3
50 4000 524288 65536 3
51 4000 524288 65536 3
52 4000 524288 65536 3
53 4000 524288 65536 3
54 4000 524288 65536 3
55 4000 524288 65536 3
56 4000 524288 65536 3
57 4000 524288 65536 3
58 4000 524288 65536 3
59 4000 524288 65536 3
60 4000 524288 65536 3
61 4000 524288 65536 3
62 4000 524288 65536 3
63 4000 524288 65536 3
64 4000 524288 65536 3
65 4000 524288 65536 3
66 4000 524288 65536 3
67 4000 524288 65536 3
68 4000 524288 65536 3
Submit
Back to Top