Tích ưu tiên

Submit solution
Points: 2.6 (partial)
Time limit: 1.0s
Memory limit: 67M
Author:
creator
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):a1,a2,...,am và (b):b1,b2,...,bn. Với mỗi truy vấn dạng uv 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 ai∗bj với 1≤i≤u và 1≤j≤v. Nói cách khác với mỗi uv bạn cần tính giá trị của max1≤i≤u1≤j≤v{ai∗bj} và min1≤i≤u1≤j≤v{ai∗bj}.

Đầu vào

Dòng đầu gồm ba số nguyên dương m, n và q (1≤m,n,q≤105), 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á 109.

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á 109.

q dòng cuối mỗi dòng chứa hai số dương u,v (1≤u≤m,1≤v≤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:

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

Đầu ra:

Copy
6 -5
10 -8
12 -9
QDUY

Comments


  • 0
    hairep2005  commented on Nov. 7, 2024, 12:10 p.m. ← edited

    Bài này ad để Memmorylimit : 67M thành ra mik bị MLE , ad cho mik hỏi nếu Memmory limit : 256M thì làm cách này ổn ko nhỉ ```

    include<bits/stdc++.h>

    using namespace std; int Min_ArrA[10005][10005] ; int Min_ArrB[10005][10005] ; int Max_ArrA[10005][10005] ; int Max_ArrB[10005][10005] ; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int m,n ,q ; cin>> m>> n >> q; int a[m] , b[n] ; for(int i=0;i<m;i++){ cin>>a[i] ; } for(int i=0;i<n;i++){ cin>>b[i] ; } for(int i=1;i<=m;i++){ Min_ArrA[i][i] = a[i-1] ; Max_ArrA[i][i] = a[i-1] ; } for(int i=1;i<=n;i++){ Min_ArrB[i][i] = b[i-1] ; Max_ArrB[i][i] = b[i-1] ; } // min int cnt = 1; for(int j=1;j<=m;j++){ for(int i=1;i+cnt<=m;i++){ Min_ArrA[i][i+cnt] = min(Min_ArrA[i][i+cnt-1],Min_ArrA[i+1][i+cnt]) ; } cnt++ ; } cnt =1 ; for(int j=1;j<=n;j++){ for(int i=1;i+cnt<=n;i++){ Min_ArrB[i][i+cnt] = min(Min_ArrB[i][i+cnt-1],Min_ArrB[i+1][i+cnt]) ; } cnt++ ; } //end min

    Copy
    // max 
 cnt = 1; 
for(int j=1;j<=m;j++){
    for(int i=1;i+cnt<=m;i++){
        Max_ArrA[i][i+cnt] = max(Max_ArrA[i][i+cnt-1],Max_ArrA[i+1][i+cnt]) ; 
    }
    cnt++ ; 
}
 cnt = 1; 
for(int j=1;j<=n;j++){
    for(int i=1;i+cnt<=n;i++){
        Max_ArrB[i][i+cnt] = max(Max_ArrB[i][i+cnt-1],Max_ArrB[i+1][i+cnt]) ; 
    }
    cnt++ ; 
}
// end max 
while(q--){
    int u , v ; cin>> u >> v; 
    cout<<max(Min_ArrA[1][u]*Min_ArrB[1][v],Max_ArrA[1][u] * Max_ArrB[1][v])<< " ";
    cout<<min({Min_ArrA[1][u]*Min_ArrB[1][v],Min_ArrA[1][u]*Max_ArrB[1][v],Min_ArrB[1][v]*Max_ArrA[1][u]}) <<endl  ;                                                              
}

    } ```