#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++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
174 ms |
117760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
161 ms |
117760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
98412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
122604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
290 ms |
121984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
51416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
104300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
47268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
128640 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
340 ms |
128768 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
391 ms |
110956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
111084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
373 ms |
113528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
343 ms |
110316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
