Submission #1593934

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

    int N,M,Q;cin>>N>>M>>Q;
    string s[N];
    int sum[N+1][M+1];
    fill(sum[0],sum[N+1],0);
    for (int i=1;i<=N;i++){
        cin>>s[i-1];
        for (int j=1;j<=M;j++){
            sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+s[i-1][j-1]-'0';
        }
    }
    int holi[N+1][M+1];
    int high[N+1][M+1];
    fill(holi[0],holi[N+1],0);
    fill(high[0],high[N+1],0);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(i*j==1)continue;
            holi[i][j]=holi[i][j-1]+holi[i-1][j]-holi[i-1][j-1];
            high[i][j]=high[i][j-1]+high[i-1][j]-high[i-1][j-1];
            if(j>=2&&s[i-1][j-1]=='1'&&s[i-1][j-2]=='1')holi[i][j]++;
            if(i>=2&&s[i-2][j-1]=='1'&&s[i-1][j-1]=='1')high[i][j]++;
        }
    }

    REP(i,Q){
        int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
        int ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
        ans   -=holi[x2][y2]-holi[x1-1][y2]-holi[x2][y1]+holi[x1-1][y1];
        ans   -=high[x2][y2]-high[x1][y2]-high[x2][y1-1]+high[x1][y1-1];
        cout<<ans<<endl;
    }


    return 0;
}

Submission Info

Judge Result