結果
問題 | No.755 Zero-Sum Rectangle |
ユーザー | homesentinel |
提出日時 | 2018-12-08 13:37:32 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 211 ms / 2,000 ms |
コード長 | 4,339 bytes |
コンパイル時間 | 1,451 ms |
コンパイル使用メモリ | 130,040 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-14 04:30:57 |
合計ジャッジ時間 | 3,054 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 211 ms
6,944 KB |
testcase_02 | AC | 94 ms
6,944 KB |
testcase_03 | AC | 84 ms
6,940 KB |
testcase_04 | AC | 77 ms
6,940 KB |
testcase_05 | AC | 72 ms
6,940 KB |
testcase_06 | AC | 69 ms
6,940 KB |
testcase_07 | AC | 68 ms
6,940 KB |
testcase_08 | AC | 68 ms
6,940 KB |
testcase_09 | AC | 69 ms
6,940 KB |
testcase_10 | AC | 68 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
evil_1 | AC | 96 ms
6,944 KB |
ソースコード
#include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #include <climits> #define rep(i, m, n) for(int i=int(m);i<int(n);i++) #define all(c) begin(c),end(c) template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; } template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; } //改造 typedef long long int ll; using namespace std; #define INF (1 << 30) - 1 #define INFl (ll)5e15 #define DEBUG 0 //デバッグする時1にしてね #define dump(x) cerr << #x << " = " << (x) << endl #define MOD 1000000007 //ここから編集する template<typename T> class Sum2d { vector<vector<T> > vv; unsigned xSize{}; unsigned ySize{}; public: Sum2d(unsigned xSize, unsigned ySize) { vector<vector<T> > vv(xSize + 2, vector<T>(ySize + 2)); this->vv = vv; this->xSize = xSize + 2; this->ySize = ySize + 2; } void add(int x, int y, T value) { x++; y++; this->vv[x][y] += value; } void set_sum() { for (int i = 0; i < xSize - 1; i++) { for (int j = 0; j < ySize; j++) { this->vv[i + 1][j] += vv[i][j]; } } for (int i = 0; i < xSize; i++) { for (int j = 0; j < ySize - 1; j++) { this->vv[i][j + 1] += vv[i][j]; } } } //[sx,tx],[sy,ty]の範囲を求めるZE T calc(int sx, int sy, int tx, int ty) { tx++; ty++; return this->vv[tx][ty] + this->vv[sx][sy] - this->vv[tx][sy] - this->vv[sx][ty]; } }; template<typename T> class Imos2d { vector<vector<T> > vv; unsigned xSize{}; unsigned ySize{}; public: Imos2d(unsigned xSize, unsigned ySize) { vector<vector<T> > vv(xSize + 2, vector<T>(ySize + 2)); this->vv = vv; this->xSize = xSize + 2; this->ySize = ySize + 2; } //[sx,tx),[sy,ty)の範囲をvalueで埋める void add(int sx, int sy, int tx, int ty, T value) { sx++; sy++; tx++; ty++; this->vv[sx][sy] += value; this->vv[tx][ty] += value; this->vv[sx][ty] -= value; this->vv[tx][sy] -= value; } void set_sum() { for (int i = 0; i < xSize - 1; i++) { for (int j = 0; j < ySize; j++) { this->vv[i + 1][j] += vv[i][j]; } } for (int i = 0; i < xSize; i++) { for (int j = 0; j < ySize - 1; j++) { this->vv[i][j + 1] += vv[i][j]; } } } T calc(int x, int y) { return this->vv[x + 1][y + 1]; } }; class Solve { public: void input() { } void solve() { input(); int N, M; cin >> N >> M; vector<vector<ll> > A(M, vector<ll>(M)); Sum2d<ll> sum2d(M, M); rep(i, 0, M) { rep(j, 0, M) { cin >> A[i][j]; sum2d.add(i, j, A[i][j]); } } sum2d.set_sum(); Imos2d<int> imos2d(M, M); for (int sx = 0; sx < M; ++sx) { for (int sy = 0; sy < M; ++sy) { for (int tx = sx; tx < M; ++tx) { for (int ty = sy; ty < M; ++ty) { if (sum2d.calc(sx, sy, tx, ty) == 0) { imos2d.add(sx, sy, tx + 1, ty + 1, 1); } } } } } imos2d.set_sum(); rep(i, 0, N) { int x, y; cin >> x >> y; --x, --y; int ans = imos2d.calc(x, y); cout << ans << endl; } } }; int main() { cin.tie(0); ios::sync_with_stdio(false); Solve().solve(); return 0; }