Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define DIM 509
- #define MODULO 16714589
- #define INF 1e18+9
- long long i,j,k,l,n,m;
- long long T[4*DIM][4*DIM],a[DIM][DIM];
- void buildtreey(long long vx,long long xtl,long long xtr,long long vy,long long ytl,long long ytr){
- if(ytl==ytr){
- if(xtl==xtr)T[vx][vy]=a[xtl][ytl];
- else T[vx][vy]=min(T[2*vx+1][vy],T[2*vx+2][vy]);
- return;
- }
- long long tm=(ytl+ytr)/2;
- buildtreey(vx,xtl,xtr,2*vy+1,ytl,tm);
- buildtreey(vx,xtl,xtr,2*vy+2,tm+1,ytr);
- T[vx][vy]=min(T[vx][2*vy+1],T[vx][2*vy+2]);
- }
- void buildtreex(long long v,long long tl,long long tr){
- if(tl!=tr){
- long long tm=(tl+tr)/2;
- buildtreex(v*2+1,tl,tm);
- buildtreex(v*2+2,tm+1,tr);
- }
- buildtreey(v,tl,tr,0,1,m);
- }
- long long queryy(long long vx,long long vy,long long tl,long long tr,long long L,long long R){
- if(tr<L || R<tl)return INF;
- if(L<=tl && tr<=R)return T[vx][vy];
- long long tm=(tl+tr)/2;
- return min(queryy(vx,2*vy+1,tl,tm,L,R),queryy(vx,2*vy+2,tm+1,tr,L,R));
- }
- long long query(long long v,long long tl,long long tr,long long Lx,long long Rx,long long Ly,long long Ry){
- if(tr<Lx || Rx<tl)return INF;
- if(Lx<=tl && tr<=Rx)return queryy(v,0,1,m,Ly,Ry);
- long long tm=(tl+tr)/2;
- return min(query(v*2+1,tl,tm,Lx,Rx,Ly,Ry),query(v*2+2,tm+1,tr,Lx,Rx,Ly,Ry));
- }
- int main()
- {
- cin>>n>>m;
- for(i=1;i<=n;i++){
- for(j=1;j<=m;j++){
- cin>>a[i][j];
- }
- }
- buildtreex(0,1,n);
- int nt,x1,x2,m1,m2;
- cin>>nt;
- for(i=1;i<=nt;i++){
- cin>>x1>>m1>>x2>>m2;
- cout<<query(0,1,n,x1,m1,x2,m2)<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement