#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int MAXN = 200000;
int nukes[MAXN][4];
void construct(vector<vector<ll>>& res, int R, int C) {
res.clear();
res.resize(R, vector<ll>(C, 0));
}
void add(vector<vector<ll>>& res, int r, int c, ll v) {
if (r < res.size() && c < res[0].size()) {
res[r][c] += v;
}
}
ll get(vector<vector<ll>>& res, int r, int c) {
if (r < res.size() && c < res[0].size() && r >= 0 && c >= 0) {
return res[r][c];
}
return 0;
}
ll ceil(ll i, ll d) {
return (i + d-1)/d;
}
void pr(vector<vector<ll>>& res) {
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[0].size(); j++) {
cerr << res[i][j] << " ";
}
cerr << '\n';
}
}
int main() {
freopen("input.in", "r", stdin);
cin.tie(0);
cin.sync_with_stdio(0);
int W, H;
cin >> W >> H;
int N;
cin >> N;
FR(i, N) {
cin >> nukes[i][1] >> nukes[i][0] >> nukes[i][2] >> nukes[i][3];
nukes[i][1]--;
nukes[i][0]--;
}
vector<vector<ll>> diagLeft;
vector<vector<ll>> diagRight;
vector<vector<ll>> hori;
vector<vector<ll>> pref;
vector<vector<ll>> initial;
construct(diagLeft, H, W);
construct(diagRight, H, W);
construct(hori, H, W);
construct(pref, H, W);
construct(initial, H, W);
FR(i, N) {
int s = (nukes[i][2] - 1)/nukes[i][3];
int st = nukes[i][2] - s*nukes[i][3];
add(diagLeft, nukes[i][0]-s, nukes[i][1]-s, -nukes[i][3]);
add(diagLeft, nukes[i][0]+s+1, nukes[i][1]+s+1, nukes[i][3]);
add(diagRight, nukes[i][0]-s, nukes[i][1]+s, -nukes[i][3]);
add(diagRight, nukes[i][0]+s+1, nukes[i][1]-s-1, nukes[i][3]);
add(hori, nukes[i][0]-s, nukes[i][1]-s, nukes[i][3]);
add(hori, nukes[i][0]-s, nukes[i][1]+s+1, -nukes[i][3]);
add(hori, nukes[i][0]+s, nukes[i][1]-s, nukes[i][3]);
add(hori, nukes[i][0] + s, nukes[i][1]+s+1, -nukes[i][3]);
add(initial, nukes[i][0]-s, nukes[i][1]-s, st);
add(initial, nukes[i][0]+s+1, nukes[i][1]-s, -st);
add(initial, nukes[i][0]-s, nukes[i][1]+s+1,-st);
add(initial, nukes[i][0]+s+1, nukes[i][1]+s+1, st);
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
hori[i][j] += get(hori, i, j-1);
diagLeft[i][j] += get(diagLeft, i-1, j-1);
diagRight[i][j] += get(diagRight, i-1, j+1);
initial[i][j] += - get(initial, i-1, j-1) + get(initial, i-1, j) + get(initial, i, j-1);
pref[i][j] = hori[i][j] + diagLeft[i][j] + diagRight[i][j] + get(pref, i-1, j);
}
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
pref[i][j] += get(pref, i-1, j);
initial[i][j] += get(pref, i-1, j);
}
}
pr(initial);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
initial[i][j] += - get(initial, i-1, j-1) + get(initial, i-1, j) + get(initial, i, j-1);
}
}
int Q;
cin >> Q;
FR(i, Q) {
int r1, r2, c1, c2;
cin >> c1 >> r1 >> c2 >> r2;
c1--, r1--, c2--, r2--;
cout << ceil(get(initial, r2, c2) - get(initial, r1-1, c2) - get(initial, r2, c1-1) + get(initial, r1-1, c1-1), (r2-r1+1)*(c2-c1+1)) << '\n';
}
return 0;
}
Compilation message
nuclearia.cpp: In function 'void add(std::vector<std::vector<long long int> >&, int, int, ll)':
nuclearia.cpp:16:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | if (r < res.size() && c < res[0].size()) {
| ~~^~~~~~~~~~~~
nuclearia.cpp:16:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | if (r < res.size() && c < res[0].size()) {
| ~~^~~~~~~~~~~~~~~
nuclearia.cpp: In function 'll get(std::vector<std::vector<long long int> >&, int, int)':
nuclearia.cpp:21:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | if (r < res.size() && c < res[0].size() && r >= 0 && c >= 0) {
| ~~^~~~~~~~~~~~
nuclearia.cpp:21:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | if (r < res.size() && c < res[0].size() && r >= 0 && c >= 0) {
| ~~^~~~~~~~~~~~~~~
nuclearia.cpp: In function 'void pr(std::vector<std::vector<long long int> >&)':
nuclearia.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < res.size(); i++) {
| ~~^~~~~~~~~~~~
nuclearia.cpp:31:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int j = 0; j < res[0].size(); j++) {
| ~~^~~~~~~~~~~~~~~
nuclearia.cpp: In function 'int main()':
nuclearia.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
38 | freopen("input.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
780 KB |
Execution killed with signal 8 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
748 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
896 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
