#include <bits/stdc++.h>
using namespace std;
//#pragma loop(no_vector)
#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<ll> > pref;
int n, m, k;
struct node{
ll ax, ay, b;
node(ll ax_ = 0, ll ay_ = 0, ll b_ = 0){
ax = ax_;
ay = ay_;
b = b_;
}
void operator+=(const node &other){
ax += other.ax;
ay += other.ay;
b += other.b;
}
void operator-=(const node &other){
ax -= other.ax;
ay -= other.ay;
b -= other.b;
}
};
vector<vector<node> > ver, diag1, diag2;
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);
/*hor.resize(n+2);
for (int i = 0; i <= n+1; i++)
hor[i].resize(m+2, node());
*/
ver.resize(n+2);
for (int i = 0; i <= n+1; i++)
ver[i].resize(m+2, node());
diag1.resize(n+2);
for (int i = 0; i <= n+1; i++)
diag1[i].resize(m+2, node());
diag2.resize(n+2);
for (int i = 0; i <= n+1; i++)
diag2[i].resize(m+2, node());
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;
int r0 = max(1, r-s), r1 = min(n, r+s);
int c0 = max(1, c-s), c1 = min(m, c+s);
// case 1
node val = node(0, b, a-c*1LL*b);
ver[r0][c0] += val;
ver[r1+1][c0] -= val;
// case 4
val = node(0, b, -a-b*1LL*c);
if (c1 < m){
ver[r0][c1+1] += val;
ver[r1+1][c1+1] -= val;
}
// case 2
val = node(b, -b, b*1LL*c-b*1LL*r);
if ((r-r0) <= (c-c0)){
diag1[r0][c-r+r0] += val;
}
else{
diag1[r-c+c0][c0] += val;
ver[r0][c0] += val;
ver[r-c+c0][c0] -= val;
}
if ((r1-r) <= (c1-c)){
diag1[r1+1][c+r1-r+1] -= val;
}
// case 3
val = node(-b, -b, b*1LL*c+b*1LL*r);
if ((r1-r) <= (c-c0)){
diag2[r1][c-r1+r] += val;
}
else{
diag2[r+c-c0][c0] += val;
ver[r+c-c0+1][c0] += val;
ver[r1+1][c0] -= val;
}
if ((r-r0) <= (c1-c)){
diag2[r0-1][c+r-r0+1] -= val;
}
}
#pragma omp parallel for collapse(2)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++)
ver[x][y] += ver[x-1][y];
#pragma omp parallel for collapse(2)
for (int y = 1; y <= m; y++)
for (int x = 1; x <= n; x++){
diag1[x][y] += diag1[x-1][y-1];
diag2[x][y] += diag2[x+1][y-1];
ver[x][y] += diag1[x][y];
ver[x][y] += diag2[x][y];
}
#pragma omp parallel for collapse(2)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++){
ver[x][y] += ver[x][y-1];
pref[x][y] = ver[x][y].ax*x + ver[x][y].ay*y + ver[x][y].b;
pref[x][y] += pref[x-1][y]+pref[x][y-1]-pref[x-1][y-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:119:0: warning: ignoring #pragma omp parallel [-Wunknown-pragmas]
#pragma omp parallel for collapse(2)
nuclearia.cpp:124:0: warning: ignoring #pragma omp parallel [-Wunknown-pragmas]
#pragma omp parallel for collapse(2)
nuclearia.cpp:134:0: warning: ignoring #pragma omp parallel [-Wunknown-pragmas]
#pragma omp parallel for collapse(2)
nuclearia.cpp: In function 'int main()':
nuclearia.cpp:44: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:46: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:144:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
nuclearia.cpp:147: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 |
523 ms |
568000 KB |
Output is correct |
| 2 |
Correct |
97 ms |
4600 KB |
Output is correct |
| 3 |
Correct |
90 ms |
3960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
553 ms |
568056 KB |
Output is correct |
| 2 |
Correct |
98 ms |
4600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
282 ms |
197008 KB |
Output is correct |
| 2 |
Correct |
97 ms |
4344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
459 ms |
233232 KB |
Output is correct |
| 2 |
Correct |
99 ms |
4780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
676 ms |
572492 KB |
Output is correct |
| 2 |
Correct |
104 ms |
5524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
358 ms |
232048 KB |
Output is correct |
| 2 |
Correct |
97 ms |
4704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
469 ms |
202244 KB |
Output is correct |
| 2 |
Correct |
103 ms |
4944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
298 ms |
157712 KB |
Output is correct |
| 2 |
Correct |
97 ms |
4344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
815 ms |
576012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
809 ms |
575764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
605 ms |
204444 KB |
Output is correct |
| 2 |
Correct |
659 ms |
204536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
664 ms |
204420 KB |
Output is correct |
| 2 |
Correct |
643 ms |
205068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
601 ms |
209592 KB |
Output is correct |
| 2 |
Correct |
541 ms |
206520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
567 ms |
204796 KB |
Output is correct |
| 2 |
Execution timed out |
1102 ms |
849224 KB |
Time limit exceeded |
