#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;
void read(int &res){
char c;
while (c = getchar(), c < '0' || c > '9'){}
res = c-'0';
while (c = getchar(), '0' <= c && c <= '9'){
res = res*10+c-'0';
}
}
int main(){
read(m), read(n), read(k);
for (int i = 0; i < k; i++)
read(arr[i].fi.se), read(arr[i].fi.fi), read(arr[i].se.fi), read(arr[i].se.se);
pref.resize(n+1);
for (int i = 0; i <= n; i++)
pref[i].resize(m+1, 0);
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;
read(q);
for (int i = 0; i < q; i++){
int x1, y1, x2, y2;
read(y1), read(x1), read(y2), read(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:124:0: warning: ignoring #pragma omp parallel [-Wunknown-pragmas]
#pragma omp parallel for collapse(2)
nuclearia.cpp:129:0: warning: ignoring #pragma omp parallel [-Wunknown-pragmas]
#pragma omp parallel for collapse(2)
nuclearia.cpp:139:0: warning: ignoring #pragma omp parallel [-Wunknown-pragmas]
#pragma omp parallel for collapse(2)
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
513 ms |
568056 KB |
Output is correct |
| 2 |
Correct |
62 ms |
3240 KB |
Output is correct |
| 3 |
Correct |
54 ms |
2808 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
516 ms |
567820 KB |
Output is correct |
| 2 |
Correct |
62 ms |
3220 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
276 ms |
196952 KB |
Output is correct |
| 2 |
Correct |
59 ms |
3192 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
459 ms |
233268 KB |
Output is correct |
| 2 |
Correct |
62 ms |
3236 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
642 ms |
571008 KB |
Output is correct |
| 2 |
Correct |
71 ms |
3612 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
326 ms |
230648 KB |
Output is correct |
| 2 |
Correct |
62 ms |
3320 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
440 ms |
201008 KB |
Output is correct |
| 2 |
Correct |
65 ms |
3548 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
269 ms |
156264 KB |
Output is correct |
| 2 |
Correct |
66 ms |
3320 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
761 ms |
574252 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
794 ms |
574396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
527 ms |
202864 KB |
Output is correct |
| 2 |
Correct |
620 ms |
203004 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
592 ms |
202916 KB |
Output is correct |
| 2 |
Correct |
570 ms |
203644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
594 ms |
208228 KB |
Output is correct |
| 2 |
Correct |
514 ms |
205308 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
498 ms |
203404 KB |
Output is correct |
| 2 |
Execution timed out |
1124 ms |
899536 KB |
Time limit exceeded |
