#include <bits/stdc++.h>
using namespace std;
const int N = 2500005;
int w, h, n, q;
long long a[4][N];
long long row[N], col[N];
long long sum[N];
int encode(int x, int y) {
return (x - 1) * h + y;
}
void updateRes(int x0, int y0, int x1, int y1, int val) {
sum[encode(x0, y0)] += val;
if (y1 < h) sum[encode(x0, y1 + 1)] -= val;
if (x1 < w) sum[encode(x1 + 1, y0)] -= val;
if (y1 < h && x1 < w) sum[encode(x1 + 1, y1 + 1)] += val;
}
void update0(int x, int y, int val, int cnt) {
// diagonal
int cntD = min(cnt - 1, min(x - 1, y - 1));
if (x < w && y < h) a[0][encode(x + 1, y + 1)] -= val;
cnt -= cntD + 1, x -= cntD, y -= cntD;
a[0][encode(x, y)] += val;
// line
int cntL;
if (x - 1 > y - 1) {
// update col 1
cntL = min(cnt, x - 1);
col[x] -= val;
x -= cntL, cnt -= cntL;
col[x] += val;
}
else {
// update row 1
cntL = min(cnt, y - 1);
row[y] -= val;
y -= cntL, cnt -= cntL;
row[y] += val;
}
if (cnt) sum[1] += val * cnt;
}
void update1(int x, int y, int val, int cnt) {
// diagonal
int cntD = min(cnt - 1, min(x - 1, h - y));
if (x < w && y > 1) a[1][encode(x + 1, y - 1)] -= val;
cnt -= cntD + 1, x -= cntD, y += cntD;
a[1][encode(x, y)] += val;
// line
if (x - 1 < h - y) {
int cntL = min(cnt, h - y);
// update row 1
if (y < h) row[y + 1] += val;
y += cntL, cnt -= cntL;
if (y < h) row[y + 1] -= val;
}
}
void update2(int x, int y, int val, int cnt) {
// diagonal
int cntD = min(cnt - 1, min(w - x, y - 1));
if (x > 1 && y < h) a[2][encode(x - 1, y + 1)] -= val;
cnt -= cntD + 1, x += cntD, y -= cntD;
a[2][encode(x, y)] += val;
// line
if (w - x > y - 1) {
int cntL = min(cnt, w - x);
// update col 1
if (x < w) col[x + 1] += val;
x += cntL, cnt -= cntL;
if (x < w) col[x + 1] -= val;
}
}
void update3(int x, int y, int val, int cnt) {
// diagonal
int cntD = min(cnt - 1, min(w - x, h - y));
if (x > 1 && y > 1) a[3][encode(x - 1, y - 1)] -= val;
x += cntD, y += cntD;
a[3][encode(x, y)] += val;
}
void updateAll() {
// row 1
for (int i = 2; i <= h; ++i) row[i] += row[i - 1];
// col 1
for (int i = 2; i <= w; ++i) col[i] += col[i - 1];
// diagonal -1, -1
for (int i = 2; i <= w; ++i) {
for (int j = 2; j <= h; ++j) {
a[0][encode(i, j)] += a[0][encode(i - 1, j - 1)];
}
}
// diagonal -1, +1
for (int i = 2; i <= w; ++i) {
for (int j = h - 1; j >= 1; --j) {
a[1][encode(i, j)] += a[1][encode(i - 1, j + 1)];
}
}
// diagonal +1, -1
for (int i = w - 1; i >= 1; --i) {
for (int j = 2; j <= h; ++j) {
a[2][encode(i, j)] += a[2][encode(i + 1, j - 1)];
}
}
for (int i = w - 1; i >= 1; --i) {
for (int j = h - 1; j >= 1; --j) {
a[3][encode(i, j)] += a[3][encode(i + 1, j + 1)];
}
}
}
void debugDiagonal(int type) {
cout << "Diagonal " << type << '\n';
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= h; ++j) {
cout << a[type][encode(i, j)] << ' ';
}
cout << '\n';
}
}
void debugRow() {
cout << "Row\n";
for (int i = 1; i <= h; ++i) cout << row[i] << ' '; cout << '\n';
}
void debugCol() {
cout << "Col\n";
for (int i = 1; i <= w; ++i) cout << row[i] << ' '; cout << '\n';
}
void calcIndividual() {
// sum -> value of cell (i, j)
// for col
for (int i = 1; i <= w; ++i) sum[encode(i, 1)] += col[i];
// for row
for (int i = 1; i <= h; ++i) sum[encode(1, i)] += row[i];
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= h; ++j) {
// for diagonal
for (int k = 0; k <= 3; ++k) {
sum[encode(i, j)] += a[k][encode(i, j)];
}
if (i > 1) sum[encode(i, j)] += sum[encode(i - 1, j)];
if (j > 1) sum[encode(i, j)] += sum[encode(i, j - 1)];
if (i > 1 && j > 1) sum[encode(i, j)] -= sum[encode(i - 1, j - 1)];
// cout << sum[encode(i, j)] << ' ';
}
// cout << '\n';
}
}
void calcSum() {
// sum -> sum values of cells from (1, 1) -> (i, j)
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= h; ++j) {
if (i > 1) sum[encode(i, j)] += sum[encode(i - 1, j)];
if (j > 1) sum[encode(i, j)] += sum[encode(i, j - 1)];
if (i > 1 && j > 1) sum[encode(i, j)] -= sum[encode(i - 1, j - 1)];
}
}
}
long long calcRes(int x0, int y0, int x1, int y1) {
long long res = sum[encode(x1, y1)];
if (x0 > 1) res -= sum[encode(x0 - 1, y1)];
if (y0 > 1) res -= sum[encode(x1, y0 - 1)];
if (x0 > 1 && y0 > 1) res += sum[encode(x0 - 1, y0 - 1)];
return res;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d %d %d", &w, &h, &n);
// update offline plants
for (int i = 1; i <= n; ++i) {
int x, y, a, b;
scanf("%d %d %d %d", &x, &y, &a, &b);
int tmp = min(a / b, max(max(x - 1, w - x), max(y - 1, h - y)));
// update all covered cells
updateRes(max(x - tmp, 1), max(y - tmp, 1), min(x + tmp, w), min(y + tmp, h), a - b * tmp);
// update diagonal -1, -1
update0(x, y, b, tmp);
// update diagonal -1, +1
if (y < h) update1(x, y + 1, -b, tmp);
// update diagonal +1, -1
if (x < w) update2(x + 1, y, -b, tmp);
// update diagonal +1, +1
if (x < w && y < h) update3(x + 1, y + 1, b, tmp);
}
// prepare for answering queries
updateAll();
// for (int i = 0; i < 4; ++i) debugDiagonal(i);
// debugRow(), debugCol();
calcIndividual();
calcSum();
// queries
int q;
scanf("%d", &q);
while (q--) {
int x0, y0, x1, y1;
scanf("%d %d %d %d", &x0, &y0, &x1, &y1);
int sz = (x1 - x0 + 1) * (y1 - y0 + 1);
long long res = calcRes(x0, y0, x1, y1);
printf("%lld\n", (res + sz / 2) / sz);
}
}
Compilation message
nuclearia.cpp: In function 'int main()':
nuclearia.cpp:184:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &w, &h, &n);
^
nuclearia.cpp:190:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &x, &y, &a, &b);
^
nuclearia.cpp:217:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
nuclearia.cpp:220:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &x0, &y0, &x1, &y1);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
96 ms |
138736 KB |
Output is correct |
| 3 |
Correct |
99 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
116 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
99 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
126 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
123 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
186 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
106 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
106 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
149 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
459 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
453 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
483 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
459 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
483 ms |
138736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
433 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
473 ms |
138736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
389 ms |
138736 KB |
Output is correct |
| 2 |
Correct |
373 ms |
138736 KB |
Output is correct |
