Submission #1779342

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
const int maxn=2000+10;
int cnt[maxn][maxn],cntr[maxn][maxn],cntd[maxn][maxn];
int query(int cnt[maxn][maxn],int x1,int y1,int x2,int y2)
{
    return cnt[x2][y2]-cnt[x2][y1-1]-cnt[x1-1][y2]+cnt[x1-1][y1-1];
}
int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(!isdigit(ch))
    {
        f=((ch=='-')?-f:f);
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f<0?-x:x;
}
int get01()
{
    char ch=getchar();
    while(ch!='0'&&ch!='1') ch=getchar();
    return ch-'0';
}
int n,m,q;
int main()
{
    memset(cnt,0,sizeof cnt);
    memset(cntd,0,sizeof cntd);
    memset(cntr,0,sizeof cntr);
    n=read();m=read();q=read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cnt[i][j]=get01();
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
            if(cnt[i][j]==1&&cnt[i][j+1]==1) cntr[i][j]=1;else cntr[i][j]=0;
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
            if(cnt[i][j]==1&&cnt[i+1][j]==1) cntd[i][j]=1;else cntd[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cnt[i][j]+=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1];
            cntr[i][j]+=cntr[i-1][j]+cntr[i][j-1]-cntr[i-1][j-1];
            cntd[i][j]+=cntd[i-1][j]+cntd[i][j-1]-cntd[i-1][j-1];
        }
    for(int i=1;i<=q;i++)
    {
        int x1=read(),y1=read(),x2=read(),y2=read();
        printf("%d\n",query(cnt,x1,y1,x2,y2)-query(cntr,x1,y1,x2,y2-1)-query(cntd,x1,y1,x2-1,y2));
    }
    return 0;
}

Submission Info

Judge Result