結果

問題 No.755 Zero-Sum Rectangle
コンテスト
ユーザー potoooooooo
提出日時 2018-12-16 23:01:36
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 210 ms / 2,000 ms
コード長 2,661 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,830 ms
コンパイル使用メモリ 175,284 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-25 06:39:55
合計ジャッジ時間 3,555 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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