Submission #69444208

---

Source Code Expand

// To scale the heights, one must embrace the fall.
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define pb emplace_back
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 505, M = (N << 1), inf = 1e16, mod = 1e9 + 7;
int n, m, a[N][N], s[N][N];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    F(i, 1, n) {
        F(j, 1, n) {
            char c;
            cin >> c;
            a[i][j] = c == '.';
        }
    }
    F(i, 1, n - 1) F(j, 1, n - 1) {
        if (a[i][j] && a[i + 1][j] && a[i][j + 1] && a[i + 1][j + 1])
            s[i][j] = 1;
        s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }

    while (m--) {
        int u, d, l, r;
        cin >> u >> d >> l >> r;
        int sum = s[d - 1][r - 1] - s[u - 1][r - 1] - s[d - 1][l - 1] + s[u - 1][l - 1];
        cout << sum << '\n';
    }
    return 0;
}

Submission Info

Judge Result