Tích ưu tiên


Submit solution

Points: 2.6 (partial)
Time limit: 1.0s
Memory limit: 67M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho hai dãy số nguyên \((a): a_1, a_2, ...,a_m\) và \((b): b_1, b_2, ..., b_n\). Với mỗi truy vấn dạng \(u\:v\) bạn cần phải tìm giá trị nhỏ nhất và lớn nhất trong tất cả các tích dạng \(a_i*b_j\) với \(1 \le i \le u\) và \(1 \le j \le v\). Nói cách khác với mỗi \(u\:v\) bạn cần tính giá trị của \(\displaystyle\max_{\substack{1 \le i \le u\\1 \le j \le v}}\{a_i*b_j\}\) và \(\displaystyle\min_{\substack{1 \le i \le u\\1 \le j \le v}}\{a_i*b_j\}\).

Đầu vào

Dòng đầu gồm ba số nguyên dương \(m\), \(n\) và \(q\) \((1 \le m, n, q \le 10^5)\), số phần tử của dãy \((a)\), \((b)\) và số truy vấn.

Dòng thứ hai gồm \(m\) số nguyên là các phần tử của dãy \((a)\) có giá trị tuyệt đối không vượt quá \(10^9\).

Dòng thứ ba gồm \(n\) số nguyên là các phần tử của dãy \((b)\) có giá trị tuyệt đối không vượt quá \(10^9\).

\(q\) dòng cuối mỗi dòng chứa hai số dương \(u, v\) \((1 \le u \le m, 1 \le v \le n)\).

Đầu ra

\(q\) dòng, mỗi dòng gồm hai số nguyên (số lớn hơn đứng trước) là trả lời của một truy vấn.

Subtask

\(30\%\) số test có \(q = 1, u = m, v = n\).

Ví dụ

Đầu vào:

6 6 3
-1 2 -3 4 -5 6
1 -2 3 -4 5 -6
1 6
2 5
3 4

Đầu ra:

6 -5
10 -8
12 -9
QDUY

Comments

There are no comments at the moment.