fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. #define mod 1000000007
  7. #define MAX 1000000000000000
  8. #define all(v) v.begin(),v.end()
  9. #define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
  10. #define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
  11. #define ii pair<ll,pair<ll,ll> >
  12. #define MP make_pair
  13. #define pb push_back
  14. #define f first
  15. #define se second
  16. #define ll int
  17. #define vi vector<ll>
  18. ll modexp(ll a,ll b){ ll res = 1; while(b > 0){  if(b & 1) res = (res * a)%mod;  a = (a * a)%mod;  b/=2;  }  return res; }
  19. #define rs resize
  20. typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > OST;
  21. #define TRACE
  22. #ifdef TRACE
  23. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  24.     template <typename Arg1>
  25.     void __f(const char* name, Arg1&& arg1){
  26.         cout << name << " : " << arg1 << endl;
  27.     }
  28.     template <typename Arg1, typename... Args>
  29.     void __f(const char* names, Arg1&& arg1, Args&&... args){
  30.         const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  31.     }
  32. #else
  33. #define trace(...)
  34. #endif
  35.  
  36. const ll N = 103,M = 503;
  37. ll t,i,j,k,n,m,q,a,b,c,d,lo,hg,mid,s,ans;
  38. ll fr[M][N][N],dp[M][N][N];
  39. int main()
  40. {
  41.     std::ios_base::sync_with_stdio(false); cin.tie(NULL);
  42.     scanf("%d",&t);
  43.     while(t--){
  44.         rep(i,0,M) rep(j,0,n + 1) rep(k,0,m + 1) dp[i][j][k] = fr[i][j][k] = 0;
  45.         scanf("%d%d%d",&n,&m,&q);
  46.         rep(i,1,n + 1) rep(j,1,m + 1){
  47.             scanf("%d",&a);
  48.             fr[a][i][j] = 1;
  49.         }
  50.         rep(k,1,M) rep(i,1,n + 1) rep(j,1,m + 1) fr[k][i][j] += (fr[k][i - 1][j] + fr[k][i][j - 1] - fr[k][i - 1][j - 1]);
  51.         rep(i,1,n + 1) rep(j,1,m + 1) rep(k,1,M) dp[k][i][j] = dp[k - 1][i][j] + fr[k][i][j];
  52.         while(q--){
  53.             scanf("%d%d%d%d",&a,&b,&c,&d);
  54.             s = (c - a + 1) * (d - b + 1);
  55.             lo = 1; hg = M - 3;
  56.             ans = -1;
  57.             while(lo <= hg){
  58.                 mid = (lo + hg) / 2;
  59.                 k = dp[mid][c][d] - dp[mid][a - 1][d] - dp[mid][c][b - 1] + dp[mid][a - 1][b - 1];
  60.                 if(k < (s + 1) / 2)
  61.                     lo = mid + 1;
  62.                 else{
  63.                     ans = mid;
  64.                     hg = mid - 1;
  65.                 }
  66.             }
  67.             printf("%d\n",ans);
  68.         }
  69.     }
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 8836KB
comments (?)
stdin
copy 
1
4 4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 2 2
1 2 3 3
1 3 4 3
stdout
copy 
2
6
7
https://ideone.com/EnCunm
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!