結果
問題 | No.755 Zero-Sum Rectangle |
ユーザー | t98slider |
提出日時 | 2023-03-31 19:33:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 197 ms / 2,000 ms |
コード長 | 2,630 bytes |
コンパイル時間 | 2,172 ms |
コンパイル使用メモリ | 183,444 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 22:30:09 |
合計ジャッジ時間 | 3,818 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 197 ms
6,944 KB |
testcase_02 | AC | 67 ms
6,940 KB |
testcase_03 | AC | 62 ms
6,940 KB |
testcase_04 | AC | 58 ms
6,944 KB |
testcase_05 | AC | 50 ms
6,940 KB |
testcase_06 | AC | 46 ms
6,944 KB |
testcase_07 | AC | 44 ms
6,940 KB |
testcase_08 | AC | 44 ms
6,944 KB |
testcase_09 | AC | 45 ms
6,940 KB |
testcase_10 | AC | 43 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,940 KB |
evil_1 | AC | 67 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; //2次元累積和 template< class T > struct CumulativeSum2D{ vector<vector<T>> data; CumulativeSum2D(int H, int W) : data(H + 1, vector<T>(W + 1, 0)) {} void add(int y, int x, T z){ y++, x++; if(y >= data.size() || x >= data[0].size())return; data[y][x] += z; } void build(){ for(int i = 1; i < data.size(); i++) { for(int j = 1; j < data[i].size(); j++) { data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1]; } } } T query(int sy, int sx, int gy, int gx){ return (data[gy][gx] - data[sy][gx] - data[gy][sx] + data[sy][sx]); } }; //2次元imos法 template<class T > struct imos2D{ vector<vector<T>> data; imos2D(int H, int W) : data(H + 1, vector<T>(W + 1, 0)) {} void add(int sy, int sx, int gy, int gx, T z){ data[gy][gx] += z; data[sy][gx] -= z; data[gy][sx] -= z; data[sy][sx] += z; } void build(){ for(int i = 0; i < data.size(); i++) { for(int j = 1; j < data[i].size(); j++) { data[i][j] += data[i][j - 1]; } } for(int i = 0; i < data[0].size(); i++) { for(int j = 1; j < data.size(); j++) { data[j][i] += data[j - 1][i]; } } } T query(int y, int x){ return data[y][x]; } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; CumulativeSum2D<ll> A(m, m); imos2D<int> B(m, m); for(int y = 0; y < m; y++){ for(int x = 0; x < m; x++){ int v; cin >> v; A.add(y, x, v); } } A.build(); for(int ly = 0; ly < m; ly++){ for(int ry = ly + 1; ry <= m; ry++){ ll s = 0; vector<pair<ll, int>> temp(m + 1); for(int x = 1; x <= m; x++){ temp[x] = make_pair(A.query(ly, 0, ry, x), x); } sort(temp.begin(), temp.end()); for(int i = 0; i < m; ){ int p = i; while(i <= m && temp[i].first == temp[p].first) i++; for(int j = p; j < i; j++){ for(int k = j + 1; k < i; k++){ B.add(ly, temp[j].second, ry, temp[k].second, 1); } } } } } B.build(); for(int i = 0; i < n; i++){ int y, x; cin >> y >> x; y--, x--; cout << B.query(y, x) << '\n'; } }