fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. using namespace std;
  6. const long long oo=1e18;
  7. const int mod=1e9+7;
  8. const int base=31;
  9. int Test=1;
  10. bool bit(int mask,int i){return (mask>>i)&1;}
  11. void home()
  12. {
  13.     if(fopen("main.inp","r")) 
  14.     freopen("main.inp","r",stdin),
  15.     freopen("main.out","w",stdout);
  16. }
  17. int n,m;
  18. int maxR[2005][2005],dp[2005][2005];
  19. int a[2005][2005],h[2005],L[2005],R[2005];
  20. void Pha(int val)
  21. {
  22.     for(int j=1;j<=m;j++)h[j]=0;
  23.     for(int i=1;i<=n;i++)
  24.     {
  25.         for(int j=1;j<=m;j++)
  26.         {
  27.             if(a[i][j]>=val&&a[i][j]-val<=1)h[j]++;
  28.             else h[j]=0;
  29.         }
  30.         vector<int>cur;
  31.         for(int j=1;j<=m;j++)
  32.         {
  33.             while(cur.size()&&h[cur.back()]>=h[j])cur.pop_back();
  34.             if(cur.size())L[j]=cur.back();
  35.             else L[j]=0;
  36.             cur.push_back(j);
  37.         }
  38.         cur.clear();
  39.         for(int j=m;j>=1;j--)
  40.         {
  41.             while(cur.size()&&h[cur.back()]>=h[j])cur.pop_back();
  42.             if(cur.size())R[j]=cur.back();
  43.             else R[j]=m+1;
  44.             cur.push_back(j);
  45.         }
  46.         for(int j=1;j<=m;j++)maxR[i][h[j]]=max(maxR[i][h[j]],(R[j]-L[j]-1)*h[j]);
  47.         for(int j=i;j>=0;j--)maxR[i][j]=max(maxR[i][j],maxR[i][j+1]-maxR[i][j+1]/(j+1));
  48.     }
  49. }
  50. void Tcmduc_VOI26()
  51. {
  52.     cin>>n>>m;
  53.     for(int i=1;i<=n;i++)
  54.     {
  55.         for(int j=1;j<=m;j++)
  56.             cin>>a[i][j];
  57.     }
  58.     Pha(0);
  59.     Pha(1);
  60.     for(int i=1;i<=n;i++)
  61.     {
  62.         for(int j=1;j<=i;j++)
  63.             maxR[i][j]=max(maxR[i][j],maxR[i-1][j-1]),
  64.             maxR[i][j]=max(maxR[i][j],maxR[i][j-1]);
  65.     }
  66.     int k;cin>>k;
  67.     while(k--)
  68.     {
  69.         int l,r;cin>>l>>r;
  70.         cout<<maxR[r][r-l+1]<<'\n';
  71.     }
  72. }
  73. signed main()
  74. {
  75.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  76.     while(Test--)Tcmduc_VOI26();
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ovSWSc
language:
C++14 (gcc 8.3)
created:
8 days 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!