結果

問題 No.755 Zero-Sum Rectangle
ユーザー potoooooooopotoooooooo
提出日時 2018-12-16 23:01:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 209 ms / 2,000 ms
コード長 2,661 bytes
コンパイル時間 1,762 ms
コンパイル使用メモリ 175,432 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-25 22:23:56
合計ジャッジ時間 3,656 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 209 ms
4,348 KB
testcase_02 AC 119 ms
4,348 KB
testcase_03 AC 109 ms
4,348 KB
testcase_04 AC 103 ms
4,348 KB
testcase_05 AC 98 ms
4,348 KB
testcase_06 AC 95 ms
4,348 KB
testcase_07 AC 95 ms
4,348 KB
testcase_08 AC 96 ms
4,348 KB
testcase_09 AC 97 ms
4,348 KB
testcase_10 AC 98 ms
4,348 KB
testcase_11 AC 1 ms
4,348 KB
evil_1 AC 121 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

// one-based numbering
template<class Numeric> struct CumulativeSum2D {
    private:
        vector< vector<Numeric> > _mat;
        int _col, _row;
    public:
        CumulativeSum2D(int col, int row) : _col(col), _row(row) {
            _mat.assign(_col+2, vector<Numeric>(_row+2, 0));
        }
        int col() const { return _col; }
        int row() const { return _row; }
        vector<Numeric> &operator[](int i) { return _mat[i]; }
        Numeric &operator() (int i, int j) { return _mat[i][j]; }
        void Accumulate() {
            for (int i = 0; i <= _col; i++) {
                for (int j = 0; j <= _row; j++) {
                    _mat[i][j+1] += _mat[i][j];
                }
            }
            for (int i = 0; i <= _col; i++) {
                for (int j = 0; j <= _row; j++) {
                    _mat[i+1][j] += _mat[i][j];
                }
            }
        }
        Numeric rangeSum(int i, int j, int u, int v) {
            return _mat[i-1][j-1] + _mat[u][v] - _mat[i-1][v] - _mat[u][j-1];
        }
        Numeric rangeSum(pair<int, int> upper_left, pair<int, int> lower_right) {
            return rangeSum(upper_left.first, upper_left.second, lower_right.first, lower_right.second);
        }
        void rangeAdd(int i, int j, int u, int v, Numeric add) {
            _mat[i][j] += add; _mat[u+1][v+1] += add;
            _mat[i][v+1] -= add; _mat[u+1][j] -= add;
        }
        void rangeAdd(pair<int, int> upper_left, pair<int, int> lower_right, Numeric add) {
            return rangeAdd(upper_left.first, upper_left.second, lower_right.first, lower_right.second, add);
        }
        void print() {
            for (int i = 0; i < _col+2; ++i) {
                for (int j = 0; j < _row+2; ++j) {
                    cout << _mat[i][j] << "\t";
                }
                cout << endl;
            }
        }
};

int main() {
    int n, m; cin >> n >> m;
    CumulativeSum2D<long long> a(m, m), count(m, m);
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    a.Accumulate();
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int u = i; u <= m; ++u) {
                for (int v = j; v <= m; ++v) {
                    if (a.rangeSum({i, j}, {u, v}) == 0) {
                        count.rangeAdd({i, j}, {u, v}, 1);
                    }
                }
            }
        }
    }
    count.Accumulate();
    for (int i = 0; i < n; ++i) {
        int p, q; cin >> p >> q;
        cout << count[p][q] << endl;
    }
    return 0;
}
0