Submission #48157278

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>

namespace {
using ModInt [[maybe_unused]] = atcoder::modint998244353;
using Num [[maybe_unused]] = long long int;
using Vec [[maybe_unused]] = std::vector<Num>;
using Set [[maybe_unused]] = std::set<Num>;
using Mset [[maybe_unused]] = std::multiset<Num>;
using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

template<typename T>
using Q [[maybe_unused]] = std::queue<T>;

template<typename T>
using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

constexpr Num Len = 1024;
Num n, q;
Num grid[Len][Len];
Num cumsum[Len][Len];

Num count_sub(Num top, Num left, Num bottom, Num right) {
    return cumsum[bottom][right] - cumsum[top][right] - cumsum[bottom][left] + cumsum[top][left];
}

Num count_full(Num bottom, Num right) {
    const auto n_full = count_sub(0, 0, n, n);
    const auto height = bottom / n;
    const auto width = right / n;
    const auto b = bottom % n;
    const auto r = right % n;

    Num total = height * width * n_full;
    total += count_sub(0, 0, n, r) * height;
    total += count_sub(0, 0, b, n) * width;
    total += count_sub(0, 0, b, r);
    return total;
}

void calc_cumsum() {
    for(Num y{1}; y<=n; ++y) {
        for(Num x{1}; x<=n; ++x) {
            cumsum[y][x] = grid[y-1][x-1];
        }
    }

    for(Num y{0}; y<=n; ++y) {
        for(Num x{1}; x<=n; ++x) {
            cumsum[y][x] += cumsum[y][x-1];
        }
    }

    for(Num x{0}; x<=n; ++x) {
        for(Num y{1}; y<=n; ++y) {
            cumsum[y][x] += cumsum[y-1][x];
        }
    }
}

void solve(std::istream& is, std::ostream& os) {
    is >> n >> q;

    for(Num y{0}; y<n; ++y) {
        std::string s;
        is >> s;
        for(Num x{0}; x<n; ++x) {
            const Num b = (s.at(x) == 'B') ? 1 : 0;
            grid[y][x] = b;
        }
    }

    calc_cumsum();

    while(q-- > 0) {
        Num a, b, c, d;
        is >> a >> b >> c >> d;
        ++c;
        ++d;

        Num total = count_full(c, d);
        total -= count_full(a, d);
        total -= count_full(c, b);
        total += count_full(a, b);
        os << total << "\n";
    }
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result