#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
const int N = 200000;
int x[N], y[N], a[N], b[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int nn, mm, n;
cin >> nn >> mm >> n;
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i] >> a[i] >> b[i];
--x[i], --y[i];
}
vector<vector<ll>> v(nn, vector<ll>(mm)), pref(nn, vector<ll>(mm));
if (nn == 1) {
vector<ll> added(mm + 1), bb(mm + 1);
auto add = [&](int l, int r, int x, int y) {
if (l > r) return;
added[l] += x;
bb[l + 1] += y;
bb[r + 1] -= y * 1LL * (r - l + 1);
added[r + 1] -= x;
};
for (int i = 0; i < n; ++i) {
int u = a[i] / b[i];
int L = max(0, y[i] - u);
add(L, y[i], a[i] - b[i] * (y[i] - L), b[i]);
int R = min(mm - 1, y[i] + u);
add(y[i] + 1, R, a[i] - b[i], -b[i]);
}
ll ad = 0;
ll sum = 0;
for (int i = 0; i < mm; ++i) {
sum += added[i];
ad += bb[i];
sum += ad;
v[0][i] = sum;
}
} else if (n * nn * 1LL * mm <= 100000000) {
for (int k = 0; k < n; ++k) {
for (int i = 0; i < nn; ++i) {
for (int j = 0; j < mm; ++j) {
v[i][j] += max(0ll, a[k] - b[k] * (ll) max(abs(i - x[k]), abs(j - y[k])));
}
}
}
}
for (int i = 0; i < nn; ++i) {
for (int j = 0; j < mm; ++j) {
pref[i][j] = v[i][j];
if (i) pref[i][j] += pref[i - 1][j];
if (j) pref[i][j] += pref[i][j - 1];
if (i && j) pref[i][j] -= pref[i - 1][j - 1];
}
}
auto get = [&pref](int x1, int y1, int x2, int y2) {
ll ans = pref[x2][y2];
if (x1) ans -= pref[x1 - 1][y2];
if (y1) ans -= pref[x2][y1 - 1];
if (x1 && y1) ans += pref[x1 - 1][y1 - 1];
return ans;
};
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
--x1, --y1, --x2, --y2;
ll sum = get(x1, y1, x2, y2);
ll S = (x2 - x1 + 1) * (ll) (y2 - y1 + 1);
cout << (sum * 2 / S + 1) / 2 << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
779 ms |
274316 KB |
Output is correct |
2 |
Correct |
60 ms |
2648 KB |
Output is correct |
3 |
Correct |
56 ms |
2300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
834 ms |
274336 KB |
Output is correct |
2 |
Correct |
63 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
196 ms |
39856 KB |
Output is correct |
2 |
Correct |
62 ms |
2624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
190 ms |
40524 KB |
Output is correct |
2 |
Incorrect |
58 ms |
3056 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
537 ms |
276428 KB |
Output is correct |
2 |
Correct |
74 ms |
3024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
720 ms |
112420 KB |
Output is correct |
2 |
Correct |
66 ms |
2660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
276 ms |
41852 KB |
Output is correct |
2 |
Correct |
72 ms |
3020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
501 ms |
57568 KB |
Output is correct |
2 |
Correct |
77 ms |
2636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
461 ms |
277916 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
464 ms |
277824 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
175 ms |
43288 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
172 ms |
43164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
197 ms |
43728 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
183 ms |
43480 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |