#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
typedef pair<ll, ll> pll;
const int len = 2e5+5;
pair<ii, ii> arr[len];
vector<vector<pll> > lazy;
vector<vector<ll> > pref;
int n, m, k;
void solve(){
int temp = 0;
if (n > m)
temp = 1;
if (temp){
for (int i = 0; i < k; i++)
swap(arr[i].fi.fi, arr[i].fi.se);
swap(n, m);
}
lazy.resize(n+1);
for (int i = 0; i <= n; i++)
lazy[i].resize(m+1, mp(0, 0));
for (int i = 0; i < k; i++){
int r = arr[i].fi.fi, c = arr[i].fi.se;
int a = arr[i].se.fi, b = arr[i].se.se;
int s = a/b;
//printf("i = %d, (r, c) = (%d, %d), (a, b) = (%d, %d)\n", i, r, c, a, b);
//printf("s = %d\n", s);
for (int x = max(1, r-s); x <= min(n, r+s); x++){
int d = abs(x-r);
//printf("x = %d, d = %d\n", x, d);
lazy[x][max(1, c-s)].fi += b;
lazy[x][max(1, c-s)].se += a-c*1LL*b;
lazy[x][max(1, c-d)].fi += 0 - (b);
lazy[x][max(1, c-d)].se += a-abs(r-x)*1LL*b - (a-c*1LL*b);
if (c+d >= m)
continue;
lazy[x][c+d].fi += -b;
lazy[x][c+d].se += a+c*1LL*b - (a-abs(r-x)*1LL*b);
if (c+s >= m)
continue;
lazy[x][c+s+1].fi += -(-b);
lazy[x][c+s+1].se += -(a+c*1LL*b);
}
}
for (int i = 1; i <= n; i++){
ll a = 0, b = 0;
for (int j = 1; j <= m; j++){
a += lazy[i][j].fi;
b += lazy[i][j].se;
if (!temp)
pref[i][j] = (a*1LL*j+b);
else
pref[j][i] = (a*1LL*j+b);
//printf("i = %d, j = %d, a = %lld, b = %lld\n", i, j, a, b);
//printf("%lld ", a*1LL*j+b);
}
//printf("\n");
}
if (temp){
swap(n, m);
}
}
int main(){
scanf("%d %d %d", &m, &n, &k);
for (int i = 0; i < k; i++)
scanf("%d %d %d %d", &arr[i].fi.se, &arr[i].fi.fi, &arr[i].se.fi, &arr[i].se.se);
pref.resize(n+1);
for (int i = 0; i <= n; i++)
pref[i].resize(m+1, 0);
solve();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
pref[i][j] += pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++){
int x1, y1, x2, y2;
scanf("%d %d %d %d", &y1, &x1, &y2, &x2);
ll sum = (pref[x2][y2]-pref[x1-1][y2]-pref[x2][y1-1]+pref[x1-1][y1-1]);
ll many = (x2-x1+1)*1LL*(y2-y1+1);
ll ans = sum/many;
if ((sum%many)*2 >= many)
ans++;
printf("%lld\n", ans);
}
return 0;
}
/*
4 5 1
3 2 9 1
*/
Compilation message
nuclearia.cpp: In function 'int main()':
nuclearia.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &m, &n, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &arr[i].fi.se, &arr[i].fi.fi, &arr[i].se.fi, &arr[i].se.se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
nuclearia.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &y1, &x1, &y2, &x2);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
117940 KB |
Output is correct |
| 2 |
Correct |
98 ms |
4600 KB |
Output is correct |
| 3 |
Correct |
91 ms |
3836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
117792 KB |
Output is correct |
| 2 |
Correct |
111 ms |
4608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
59128 KB |
Output is correct |
| 2 |
Correct |
97 ms |
4424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
66124 KB |
Output is correct |
| 2 |
Correct |
100 ms |
4728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
266 ms |
123720 KB |
Output is correct |
| 2 |
Correct |
111 ms |
5364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
53172 KB |
Output is correct |
| 2 |
Correct |
102 ms |
4728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
248 ms |
65132 KB |
Output is correct |
| 2 |
Correct |
105 ms |
5116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
182 ms |
41516 KB |
Output is correct |
| 2 |
Correct |
96 ms |
4344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
369 ms |
130664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
367 ms |
130740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
66680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1062 ms |
66444 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
67692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
66184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
