#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define oo 1000000000
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int w, h; cin >> w >> h;
int n; cin >> n;
vector<vector<ll>> rad(w+1, vector<ll>(h+1));
for (int i = 0; i < n; ++i) {
int x, y; ll a, b; cin >> x >> y >> a >> b;
for (int j = 1; j <= w; ++j) {
for (int k = 1; k <= h; ++k) {
rad[j][k] += max(0ll, a - b * max(1ll * abs(j - x), 1ll * abs(k - y)));
}
}
}
vector<vector<ll>> pref(w+1, vector<ll>(h+1));
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= h; ++j) {
pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + rad[i][j];
}
}
int q; cin >> q;
for (int i = 0; i < q; ++i) {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
ll cur = pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
ll cnt = 1ll * (x2 - x1 + 1) * (y2 - y1 + 1);
//cerr << cur << " " << cnt << "\n";
ll res = cur / cnt;
ll k = cnt / 2;
if (cnt % 2 == 1) k++;
if (cur % cnt >= k) res++;
cout << res << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
878 ms |
274248 KB |
Output is correct |
2 |
Correct |
92 ms |
2652 KB |
Output is correct |
3 |
Correct |
80 ms |
2196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
889 ms |
274248 KB |
Output is correct |
2 |
Correct |
84 ms |
2728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
227 ms |
39772 KB |
Output is correct |
2 |
Correct |
82 ms |
2708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
229 ms |
42424 KB |
Output is correct |
2 |
Correct |
94 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
627 ms |
276492 KB |
Output is correct |
2 |
Correct |
99 ms |
5296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
818 ms |
112820 KB |
Output is correct |
2 |
Correct |
83 ms |
4576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
365 ms |
41988 KB |
Output is correct |
2 |
Correct |
90 ms |
2820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
537 ms |
57400 KB |
Output is correct |
2 |
Correct |
87 ms |
2628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1103 ms |
137224 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1097 ms |
137212 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1090 ms |
20044 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1092 ms |
19916 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1087 ms |
20556 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1086 ms |
20044 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |