Another Random Contest 1 P2 - Two Sequences

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Given two sequences filled with non-negative integers, A and B, of length N, you will answer Q queries, each consisting of two numbers, l_i and r_i. For each query, find a K where l_i \le K \le r_i-1 that will minimize \max(A_{l_i} + A_{l_i+1} + \dots + A_{K-1} + A_K, B_{K+1} + B_{K+2} + \dots + B_{r_i-1} + B_{r_i}) and output the minimized value.

Constraints

For all subtasks:

2 \le N \le 2 \times 10^5

1 \le Q \le 2 \times 10^5

1 \le l_i < r_i \le N

0 \le A_i, B_i \le 10^9

Subtask 1 [20%]

2 \le N \le 5 \times 10^3

1 \le Q \le 5 \times 10^3

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line consists of two integers N and Q, the length of the sequences and the number of queries.

The next two lines consist of N integers.

The following Q lines consist of two integers l_i and r_i.

Output Specification

Output the minimized value for each query on Q separate lines.

Sample Input

4 4
7 5 3 5
6 2 9 1
1 2
2 3
3 4
1 2

Sample Output

7
9
3
7

Comments

There are no comments at the moment.