Submission #1758176

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iomanip>
using namespace std;
 
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

int N,M,Q;
char S[2010][2010];
int V[2010][2010];
int X[2010][2010];
int Y[2010][2010];

int cnt_ver(int x1, int y1, int x2, int y2) {
    x1--; y1--;
    return V[y2][x2] - V[y2][x1] - V[y1][x2] + V[y1][x1];
}

int cnt_edge(int x1, int y1, int x2, int y2) {
    x1--; y1--;
    int a = X[y2][x2] - X[y2][x1 + 1] - X[y1][x2] + X[y1][x1 + 1];
    int b = Y[y2][x2] - Y[y2][x1] - Y[y1 + 1][x2] + Y[y1 + 1][x1];
    return a + b;
}

int main() {
 
    cin >> N >> M >> Q;
    vector < string > St(N);
    REP(i,N) cin >> St[i];
    REP(i,N) REP(j,M) S[i + 1][j + 1] = St[i][j];

    REP(i,N) REP(j,M) V[i + 1][j + 1] = S[i + 1][j + 1] - '0';

    N += 2; M += 2;
    REP(i,N) REP(j,M) V[i + 1][j] = V[i + 1][j] + V[i][j];
    REP(i,N) REP(j,M) V[i][j + 1] = V[i][j + 1] + V[i][j];

    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (S[i][j] == '1' && S[i - 1][j] == '1') Y[i][j] = 1;
        }
    }

    REP(i,N) REP(j,M) Y[i + 1][j] = Y[i + 1][j] + Y[i][j];
    REP(i,N) REP(j,M) Y[i][j + 1] = Y[i][j + 1] + Y[i][j];

    for (int i = 1; i <= N; i++) {
        for (int j = 2; j <= M; j++) {
            if (S[i][j] == '1' && S[i][j - 1] == '1') X[i][j] = 1;
        }
    }

    REP(i,N) REP(j,M) X[i + 1][j] = X[i + 1][j] + X[i][j];
    REP(i,N) REP(j,M) X[i][j + 1] = X[i][j + 1] + X[i][j];

    REP(i,Q) {
        int x1,y1,x2,y2;
        cin >> y1 >> x1 >> y2 >> x2;
        cout << cnt_ver(x1, y1, x2, y2) - cnt_edge(x1, y1, x2, y2) << endl;
    }
 
    return 0;
}

Submission Info

Judge Result