Submission #1556991

---

Source Code Expand

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fr first
#define sc second
typedef long long ll;
const long long llinf=LLONG_MAX;
const int inf=INT_MAX;
const int nmax=2e3+5;
const int mod=1e9+7;
using namespace std;
int n,m,q,dp1[nmax][nmax],dp2[nmax][nmax],dp3[nmax][nmax],i,j;
char a[nmax][nmax];
int main()
{
	//freopen("sol.in","r",stdin);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m>>q;
    for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
	 {
        cin>>a[i][j];
        dp1[i][j]=dp1[i-1][j]+dp1[i][j-1]-dp1[i-1][j-1]+(int)(a[i][j]=='1');
        dp2[i][j]=dp2[i-1][j]+dp2[i][j-1]-dp2[i-1][j-1]+(int)(a[i][j]=='1' && a[i][j-1]=='1');
        dp3[i][j]=dp3[i-1][j]+dp3[i][j-1]-dp3[i-1][j-1]+(int)(a[i][j]=='1' && a[i-1][j]=='1');
     }
    while(q--)
    {
    	int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<dp1[x2][y2]-dp1[x1-1][y2]-dp1[x2][y1-1]+dp1[x1-1][y1-1]-(dp2[x2][y2]-dp2[x1-1][y2]-dp2[x2][y1]+dp2[x1-1][y1])-(dp3[x2][y2]-dp3[x1][y2]-dp3[x2][y1-1]+dp3[x1][y1-1])<<endl;
    }
	return 0;
}

Submission Info

Judge Result