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): 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


  • 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

    // 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  ;                                                              
}

    } ```