#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
///freopen ("input.txt", "r", stdin);
bool Inverse = 0;
int n, m;
cin >> n >> m;
if (n > m) {
Inverse = 1;
swap(n, m);
}
assert(n <= m);
vector<vector<ll>> deri(n + 2, vector<ll> (m + 2, 0)),
jmen(n + 2, vector<ll> (m + 2, 0)),
difs(n + 2, vector<ll> (m + 2, 0)),
v(n + 2, vector<ll> (m + 2, 0));
function<void(int, int, int, int, int, int)> proc = [&] (int dist, int r, int c, int a, int b, int rect_dim) {
int L = max(1, c - dist), R = min(m, c + dist);
assert(dist + 1 <= rect_dim);
if (dist + 1 <= min(rect_dim, m - c)) {
L = c + dist + 1;
R = min(c + rect_dim, m);
assert(L <= R);
jmen[r][L] += (a + 1LL * b * c);
jmen[r][R + 1] -= (a + 1LL * b * c);
difs[r][L] -= 1LL * b * L;
deri[r][L + 1] -= b;
deri[r][R + 1] += b;
difs[r][R + 1] += 1LL * b * R;
}
if (dist + 1 <= min(rect_dim, c - 1)) {
L = max(c - rect_dim, 1);
R = c - dist - 1;
assert(L <= R);
jmen[r][L] += (a - 1LL * b * c);
jmen[r][R + 1] -= (a - 1LL * b * c);
difs[r][L] += 1LL * b * L;
deri[r][L + 1] += b;
deri[r][R + 1] -= b;
difs[r][R + 1] -= 1LL * b * R;
}
};
int ops;
cin >> ops;
for (int i = 1; i <= ops; i++) {
int r1, c, a, b, rect_dim;
cin >> r1 >> c >> a >> b;
if (Inverse) {
swap(r1, c);
}
rect_dim = a / b;
for (int dist = 0; (r1 + dist <= n || r1 - dist >= 1) && dist <= rect_dim - 1; dist++) {
if (r1 + dist <= n) {
int L = max(1, c - dist), R = min(m, c + dist);
proc(dist, r1 + dist, c, a, b, rect_dim);
}
if (r1 - dist >= 1 && dist >= 1) {
int L = max(1, c - dist), R = min(m, c + dist);
proc(dist, r1 - dist, c, a, b, rect_dim);
}
}
for (int dist = 0; (r1 + dist <= n || r1 - dist >= 1) && dist <= rect_dim; dist++) {
if (r1 + dist <= n) {
int L = max(1, c - dist), R = min(m, c + dist);
jmen[r1 + dist][L] += (a - dist * b);
jmen[r1 + dist][R + 1] -= (a - dist * b);
}
if (r1 - dist >= 1 && dist >= 1) {
int L = max(1, c - dist), R = min(m, c + dist);
jmen[r1 - dist][L] += (a - dist * b);
jmen[r1 - dist][R + 1] -= (a - dist * b);
}
}
}
for (int r = 1; r <= n; r++) {
for (int c = 1; c <= m; c++) {
deri[r][c] += deri[r][c - 1];
difs[r][c] += deri[r][c];
difs[r][c] += difs[r][c - 1];
jmen[r][c] += jmen[r][c - 1];
v[r][c] += jmen[r][c];
v[r][c] += difs[r][c];
}
}
{
for (int i = 1; i <= n; i++) {
ll cur = 0;
for (int j = 1; j <= m; j++) {
cur += v[i][j];
v[i][j] = v[i - 1][j] + cur;
}
}
}
int q;
cin >> q;
while (q--) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
if (Inverse) {
swap(r1, c1);
swap(r2, c2);
}
ll total = v[r2][c2] - v[r1 - 1][c2] - v[r2][c1 - 1] + v[r1 - 1][c1 - 1];
ll area = (r2 - r1 + 1) * (c2 - c1 + 1);
cout << total / area + (total % area >= area - total % area) << "\n";
}
}
Compilation message
nuclearia.cpp: In function 'int main()':
nuclearia.cpp:64:13: warning: unused variable 'L' [-Wunused-variable]
64 | int L = max(1, c - dist), R = min(m, c + dist);
| ^
nuclearia.cpp:64:35: warning: unused variable 'R' [-Wunused-variable]
64 | int L = max(1, c - dist), R = min(m, c + dist);
| ^
nuclearia.cpp:68:13: warning: unused variable 'L' [-Wunused-variable]
68 | int L = max(1, c - dist), R = min(m, c + dist);
| ^
nuclearia.cpp:68:35: warning: unused variable 'R' [-Wunused-variable]
68 | int L = max(1, c - dist), R = min(m, c + dist);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
254664 KB |
Output is correct |
| 2 |
Correct |
58 ms |
2708 KB |
Output is correct |
| 3 |
Correct |
55 ms |
2272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
254660 KB |
Output is correct |
| 2 |
Correct |
61 ms |
2696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
78924 KB |
Output is correct |
| 2 |
Correct |
70 ms |
2764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
87464 KB |
Output is correct |
| 2 |
Correct |
56 ms |
2704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
239 ms |
256948 KB |
Output is correct |
| 2 |
Correct |
88 ms |
2908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
104468 KB |
Output is correct |
| 2 |
Correct |
73 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
81416 KB |
Output is correct |
| 2 |
Correct |
59 ms |
2896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
69244 KB |
Output is correct |
| 2 |
Correct |
59 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
358 ms |
257024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
325 ms |
257116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1097 ms |
78924 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
78904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1098 ms |
80752 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1081 ms |
79000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
