test/yukicoder/755.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://yukicoder.me/problems/no/755

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/755"
#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP2(i, s, n) for (int i = (s); i < (n); i++)

#include "library/datastructure/2D/CumulativeSum.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    std::vector v(m, std::vector<int>(m));
    REP (i, m)
        REP (j, m)
            std::cin >> v[i][j];
    CumulativeSum2D C(v);

    REP (_, n) {
        int y, x;
        std::cin >> y >> x;
        y--;
        x--;
        int ans = 0;
        REP (u, y + 1)
            REP2(d, y + 1, m + 1)
        REP (l, x + 1)
            REP2(r, x + 1, m + 1) ans += !C.sum(u, d, l, r);
        std::cout << ans << "\n";
    }
}

#line 1 "test/yukicoder/755.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/755"
#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP2(i, s, n) for (int i = (s); i < (n); i++)

#line 1 "library/datastructure/2D/CumulativeSum.hpp"
template <typename T> class CumulativeSum2D {
    using U = std::conditional_t<std::is_same_v<T, int>, long long, T>;
    int h, w;
    std::vector<std::vector<U>> A;
    bool prepared;

  public:
    CumulativeSum2D(int h = 0, int w = 0)
        : h(h), w(w), A(h + 1, std::vector<U>(w + 1, 0)), prepared(false) {}
    CumulativeSum2D(const std::vector<std::vector<T>> &v)
        : h(v.size()), w(v[0].size()), A(h + 1, std::vector<U>(w + 1, 0)),
          prepared(false) {
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                A[i + 1][j + 1] = v[i][j];
        build();
    }
    void add(int y, int x, const T &val = 1) {
        assert(!prepared);
        assert(0 <= y and y < h and 0 <= x and x < w);
        A[y + 1][x + 1] += val;
    }
    void build() {
        assert(!prepared);
        prepared = true;
        for (int i = 0; i < h; i++)
            for (int j = 0; j <= w; j++)
                A[i + 1][j] += A[i][j];
        for (int i = 0; i <= h; i++)
            for (int j = 0; j < w; j++)
                A[i][j + 1] += A[i][j];
    }
    U sum(int u, int d, int l, int r) {
        assert(prepared);
        assert(0 <= u and u <= d and u <= h);
        assert(0 <= l and l <= r and r <= w);
        return A[d][r] - A[d][l] - A[u][r] + A[u][l];
    }
    U sum() {
        assert(prepared);
        return A.back().back();
    }
};
#line 8 "test/yukicoder/755.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    std::vector v(m, std::vector<int>(m));
    REP (i, m)
        REP (j, m)
            std::cin >> v[i][j];
    CumulativeSum2D C(v);

    REP (_, n) {
        int y, x;
        std::cin >> y >> x;
        y--;
        x--;
        int ans = 0;
        REP (u, y + 1)
            REP2(d, y + 1, m + 1)
        REP (l, x + 1)
            REP2(r, x + 1, m + 1) ans += !C.sum(u, d, l, r);
        std::cout << ans << "\n";
    }
}