This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl
typedef long long ll;
int w, h, n, q;
vector<vector<ll>> s, a, b;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> w >> h;
w += 4;
h += 4;
bool flip = false;
if (w > h) {
swap(w, h);
flip = true;
}
s.resize(w);
a.resize(w);
b.resize(w);
for (int i = 0; i < w; i++) {
s[i].resize(h);
a[i].resize(h);
b[i].resize(h);
}
cin >> n;
int x, y, k, lo, hi, l, r;
ll ai, bi;
int absj;
for (int i = 0; i < n; i++) {
cin >> x >> y >> ai >> bi;
if (flip) swap(x, y);
k = ai / bi;
lo = max(1, y - k);
hi = min(h - 2, y + k + 1);
for (int j = max(-k, -x + 1); j <= min(k, w - 2 - x); j++) {
absj = abs(j);
l = max(lo, y - absj);
r = min(hi, y + absj + 1);
a[x + j][lo] += ai - bi * y;
a[x + j][l] += bi * (y - absj);
a[x + j][r] += bi * (y + absj);
a[x + j][hi] += -ai - bi * y;
b[x + j][lo] += bi;
b[x + j][l] -= bi;
b[x + j][r] -= bi;
b[x + j][hi] += bi;
}
}
// assert(false);
for (int i = 1; i < w; i++) {
for (int j = 1; j < h; j++) {
a[i][j] += a[i][j - 1];
b[i][j] += b[i][j - 1];
s[i][j] = a[i][j] + b[i][j] * j
+ s[i - 1][j]
+ s[i][j - 1]
- s[i - 1][j - 1];
}
}
cin >> q;
for (int i = 0; i < q; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (flip) {
swap(x1, y1);
swap(x2, y2);
}
ll sum = s[x2][y2]
- s[x1 - 1][y2]
- s[x2][y1 - 1]
+ s[x1 - 1][y1 - 1];
ll cnt = (x2 - x1 + 1) * (y2 - y1 + 1);
cout << (sum + cnt / 2) / cnt << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |