Submission #8399895

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1e9+7;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){
        a=b;
        return true;
    }
    return false;
}

int main(){
    int N,M,Q;
    cin >> N >> M >> Q;
    vector<string> S(N); 
    rep(i,N) cin >> S[i];
    vector<vector<int>> blue(N+1,vector<int>(M+1,0));
    rep(i,N) rep(j,M) if (S[i][j]=='1') ++blue[i+1][j+1];
    rep(i,N+1) rep(j,M) blue[i][j+1]+=blue[i][j];
    rep(j,M+1) rep(i,N) blue[i+1][j]+=blue[i][j];
    vector<vector<int>> eh(N+1,vector<int>(M,0)),ew(N,vector<int>(M+1,0));
    rep(i,N) rep(j,M-1) if (S[i][j]=='1'&&S[i][j+1]=='1') ++eh[i+1][j+1];
    rep(i,N+1) rep(j,M-1) eh[i][j+1]+=eh[i][j];
    rep(j,M) rep(i,N) eh[i+1][j]+=eh[i][j];
    rep(j,M) rep(i,N-1) if (S[i][j]=='1'&&S[i+1][j]=='1') ++ew[i+1][j+1];
    rep(j,M+1) rep(i,N-1) ew[i+1][j]+=ew[i][j];
    rep(i,N) rep(j,M) ew[i][j+1]+=ew[i][j];
    rep(i,Q){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        int node=blue[c][d]-blue[c][b-1]-blue[a-1][d]+blue[a-1][b-1];
        int edge=eh[c][d-1]-eh[a-1][d-1]-eh[c][b-1]+eh[a-1][b-1];
        edge+=ew[c-1][d]-ew[a-1][d]-ew[c-1][b-1]+ew[a-1][b-1];
        cout << node-edge << endl;
    }
}

Submission Info

Judge Result