| 12345678 |
- #include <algorithm>
- #include <array>
- #include <iostream>
- #include <limits>
- #include <vector>
- using namespace std;const long long INF=(1LL<<62);
- struct Table{int n,lg;vector<vector<long long>>mn,mx,pos,neg;Table(const vector<long long>&a){n=a.size();lg=1;while((1<<lg)<=n)++lg;mn.assign(lg,vector<long long>(n));mx=pos=neg=mn;for(int i=0;i<n;++i){mn[0][i]=mx[0][i]=a[i];pos[0][i]=a[i]>=0?a[i]:INF;neg[0][i]=a[i]<=0?a[i]:-INF;}for(int j=1;j<lg;++j)for(int i=0;i+(1<<j)<=n;++i){int h=1<<(j-1);mn[j][i]=min(mn[j-1][i],mn[j-1][i+h]);mx[j][i]=max(mx[j-1][i],mx[j-1][i+h]);pos[j][i]=min(pos[j-1][i],pos[j-1][i+h]);neg[j][i]=max(neg[j-1][i],neg[j-1][i+h]);}}array<long long,4>query(int l,int r){int j=31-__builtin_clz(r-l+1),p=r-(1<<j)+1;return{min(mn[j][l],mn[j][p]),max(mx[j][l],mx[j][p]),min(pos[j][l],pos[j][p]),max(neg[j][l],neg[j][p])};}};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m,q;cin>>n>>m>>q;vector<long long>a(n),b(m);for(auto&x:a)cin>>x;for(auto&x:b)cin>>x;Table A(a),B(b);while(q--){int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;auto x=A.query(--l1,--r1),y=B.query(--l2,--r2);long long ans=-INF;for(long long v:x)if(v>-INF&&v<INF)ans=max(ans,min(v*y[0],v*y[1]));cout<<ans<<'\n';}}
|
