Submission #8399718

---

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];
    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-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,Q){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        int node=0,edge=0;
        rep2(i,a,c+1) node+=blue[i][d]-blue[i][b-1];
        rep2(i,a,c+1) edge+=eh[i][d-1]-eh[i][b-1];
        rep2(i,b,d+1) edge+=ew[c-1][i]-ew[a-1][i];
        cout << node-edge << endl;
    }
}

Submission Info

Judge Result