//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define pb push_back
#define s second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long double ld;
//mt19937 rng(std::chrono::steady_clock().now().time_since_epoch().count());
const int MAXN = 2500100;
int w, h, n, q;
vector<vl> grid;
vector<vl> pref;
vl tmp;
ll d (ll x1, ll y11, ll x2, ll y2) {
return max(abs(x1-x2), abs(y11-y2));
}
int getmxD (ll a, ll b) {
return (a/b);
}
vector<pair<int, pll>> x0[MAXN], x1[MAXN];
vector<pair<int, pll>> yy0[MAXN], yy1[MAXN];
void addPlant (ll x, ll y, ll a, ll b) {
int mxd = getmxD(a, b);
int istr0, istr1;
/// x
istr0 = h+y-x;
istr1 = x+y;
int frx = max(1ll, x-mxd);
int tox = min((ll)h, x+mxd);
/// [frx; x], istr0
if (x != (frx-1)) {
x0[x].pb({istr0, {b, a-b*x}});
x0[frx-1].pb({istr0, {-b, -a+b*x}});
}
/// [frx; x], istr1
if (frx != (x+1)) {
x1[frx].pb({istr1+1, {-b, -a+b*x}});
x1[x+1].pb({istr1+1, {b, a-b*x}});
}
/// (x; tox], istr0
if (tox != x) {
x0[tox].pb({istr0+1, {+b, -a-b*x}});
x0[x].pb({istr0+1, {-b, +a+b*x}});
}
/// (x; tox], istr1
if ((x+1) != (tox+1)) {
x1[x+1].pb({istr1, {-b, a+b*x}});
x1[tox+1].pb({istr1, {b, -a-b*x}});
}
/// y
istr0 = w+x-y;
istr1 = x+y;
int fry = max(1ll, y-mxd);
int toy = min((ll)w, y+mxd);
/// [y-mxd; y), istr0
if ((y-1) != (fry-1)) {
yy0[y-1].pb({istr0+1, {b, a-b*y}});
yy0[fry-1].pb({istr0+1, {-b, -a+b*y}});
}
/// [y-mxd; y), istr1
if (fry != y) {
yy1[fry].pb({istr1, {-b, -a+b*y}});
yy1[y].pb({istr1, {b, a-b*y}});
}
/// (y; y+mxd], istr0
if (toy != y) {
yy0[toy].pb({istr0, {b, -a-b*y}});
yy0[y].pb({istr0, {-b, a+b*y}});
}
/// (y; y+mxd], istr1
if ((y+1) != (toy+1)) {
yy1[y+1].pb({istr1+1, {-b, a+b*y}});
yy1[toy+1].pb({istr1+1, {b, -a-b*y}});
}
}
ll prefk[MAXN], prefb[MAXN];
ll sk[MAXN], sb[MAXN];
void calcGrid () {
/// x, istr0
/// (x=h -> x=1, y=1->y=w)
FOR(i, 0, h+w+5) sk[i] = sb[i] = prefk[i] = prefb[i] = 0;
for (int x = h; x > 0; x--) {
int fr = h+1-x;
int to = h+w-x;
// cout << "X = " << x << " fr = " << fr << endl;
// if (fr-2 >= 0) sk[fr-1] += sk[fr-2];
// if (fr-2 >= 0) sb[fr-1] += sb[fr-2];
for (auto p : x0[x]) {
int id = p.f;
ll k = p.s.f;
ll b = p.s.s;
if (id < fr) {
sk[fr-1] += k;
sb[fr-1] += b;
}
prefb[id]+=b;
prefk[id]+=k;
}
FOR(istr, fr, to) {
sk[istr] = sk[istr-1] + prefk[istr];
sb[istr] = sb[istr-1] + prefb[istr];
}
FOR(y, 1, w) {
int istr = h+y-x;
ll cur = sk[istr] * x + sb[istr];
// cout << " (x, istr0) x = " << x << " y = " << y << " cur = " << cur << endl;
grid[x][y] += cur;
}
}
/// x, istr1
/// (x=1 -> x=h, y=1->y=w)
FOR(i, 0, h+w+5) sk[i] = sb[i] = prefk[i] = prefb[i] = 0;
for (int x = 1; x <= h; x++) {
int fr = x+1;
int to = x+w;
// cout << "X = " << x << " fr = " << fr << endl;
// if (fr-2 >= 0) sk[fr-1] += sk[fr-2];
// if (fr-2 >= 0) sb[fr-1] += sb[fr-2];
for (auto p : x1[x]) {
//cout <<" is " << endl;
int id = p.f;
ll k = p.s.f;
ll b = p.s.s;
if (id < fr) {
sk[fr-1] += k;
sb[fr-1] += b;
}
prefb[id]+=b;
prefk[id]+=k;
}
FOR(istr, fr, to) {
sk[istr] = sk[istr-1] + prefk[istr];
sb[istr] = sb[istr-1] + prefb[istr];
// cout << " istr=" << istr << " sk = " << sk[istr] << " sb = " << sb[istr] << endl;
}
FOR(y, 1, w) {
int istr = x+y;
ll cur = sk[istr] * x + sb[istr];
// cout << " (x, istr1) x = " << x << " y = " << y << " cur = " << cur << endl;
grid[x][y] += cur;
}
}
/// y, istr0
/// (y=w -> y=1, x=1->x=h)
FOR(i, 0, h+w+5) sk[i] = sb[i] = prefk[i] = prefb[i] = 0;
for (int y = w; y > 0; y--) {
int fr = w+1-y;
int to = w+h-y;
// cout << "X = " << x << " fr = " << fr << endl;
// if (fr-2 >= 0) sk[fr-1] += sk[fr-2];
// if (fr-2 >= 0) sb[fr-1] += sb[fr-2];
for (auto p : yy0[y]) {
int id = p.f;
ll k = p.s.f;
ll b = p.s.s;
if (id < fr) {
sk[fr-1] += k;
sb[fr-1] += b;
}
prefb[id]+=b;
prefk[id]+=k;
}
FOR(istr, fr, to) {
sk[istr] = sk[istr-1] + prefk[istr];
sb[istr] = sb[istr-1] + prefb[istr];
}
FOR(x, 1, h) {
int istr = w+x-y;
ll cur = sk[istr] * y + sb[istr];
// cout << " (x, istr0) x = " << x << " y = " << y << " cur = " << cur << endl;
grid[x][y] += cur;
}
}
/// y, istr1
/// (y=1 -> y=w, x=1->x=h)
FOR(i, 0, h+w+5) sk[i] = sb[i] = prefk[i] = prefb[i] = 0;
for (int y = 1; y <= w; y++) {
int fr = y+1;
int to = y+h;
// cout << "X = " << x << " fr = " << fr << endl;
// if (fr-2 >= 0) sk[fr-1] += sk[fr-2];
// if (fr-2 >= 0) sb[fr-1] += sb[fr-2];
for (auto p : yy1[y]) {
//cout <<" is " << endl;
int id = p.f;
ll k = p.s.f;
ll b = p.s.s;
if (id < fr) {
sk[fr-1] += k;
sb[fr-1] += b;
}
prefb[id]+=b;
prefk[id]+=k;
}
FOR(istr, fr, to) {
sk[istr] = sk[istr-1] + prefk[istr];
sb[istr] = sb[istr-1] + prefb[istr];
// cout << " istr=" << istr << " sk = " << sk[istr] << " sb = " << sb[istr] << endl;
}
FOR(x, 1, h) {
int istr = x+y;
ll cur = sk[istr] * y + sb[istr];
// cout << " (x, istr1) x = " << x << " y = " << y << " cur = " << cur << endl;
grid[x][y] += cur;
}
}
}
void calcPref () {
FOR(i, 1, h) {
ll pr = 0;
FOR(j, 1, w) {
pref[i][j] += pref[i-1][j];
pr += grid[i][j];
pref[i][j] += pr;
}
}
}
ll sum (int x1, int y11, int x2, int y2) {
ll ret = pref[x2][y2];
ret -= pref[x1-1][y2];
ret -= pref[x2][y11-1];
ret += pref[x1-1][y11-1];
return ret;
}
int main()
{
FAST_IO;
cin >> w >> h;
REP(w+1) tmp.pb(0);
REP(h+1) {
grid.pb(tmp);
pref.pb(tmp);
}
cin >> n;
REP(n) {
int x, y;
ll a, b;
cin >> y >> x >> a >> b;
//swap(x, y);
addPlant (x, y, a, b);
}
calcGrid();
calcPref();
//FOR(i, 1, h) FOR(j, 1, w) cout << " i = " << i << " j = " << j << " grid = " << grid[i][j]<< " pref = " << pref[i][j] << endl;
/* cout << " grid:" << endl;
FOR(i, 1, h) {
FOR(j, 1, w) cout << grid[i][j] << " ";
cout << endl;
}
cout << " pref:" << endl;
FOR(i, 1, h) {
FOR(j, 1, w) cout << pref[i][j] << " ";
cout << endl;
} */
cin >> q;
REP(q) {
int x1, y11, x2, y2;
cin >> y11 >> x1 >> y2 >> x2;
// swap(x1, y11);
//swap(x2, y2);
ll s = sum(x1, y11, x2, y2);
ll sz = ((ll)(x2-x1+1)) * ((ll)(y2-y11+1));
ll ans = (s+(sz/2))/sz;
cout << ans << "\n";
// cout <<endl;
}
return 0;
}
/*
4 1
2
1 1 5 1
3 1 8 7
4 1
1
3 1 8 7
grid:
0 1 8 1
4 1
1
1 1 5 1
grid:
5 4 3 2
1 4
1
1 3 8 7
grid:
0
1
8
1
1 4
1
1 1 5 1
grid:
5
4
3
2
4 3
1
3 2 4 2
grid:
0 2 2 2
0 2 4 2
0 2 2 2
4 3
1
1 1 7 3
grid:
7 4 1 0
4 4 1 0
1 1 1 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
306 ms |
411444 KB |
Output is correct |
| 2 |
Correct |
192 ms |
239520 KB |
Output is correct |
| 3 |
Correct |
192 ms |
238796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
292 ms |
411424 KB |
Output is correct |
| 2 |
Correct |
185 ms |
239560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
274724 KB |
Output is correct |
| 2 |
Correct |
169 ms |
239288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
288032 KB |
Output is correct |
| 2 |
Correct |
230 ms |
239436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
428 ms |
417364 KB |
Output is correct |
| 2 |
Correct |
205 ms |
240444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
287 ms |
311560 KB |
Output is correct |
| 2 |
Correct |
179 ms |
239492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
343 ms |
280808 KB |
Output is correct |
| 2 |
Correct |
208 ms |
240204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
311 ms |
284216 KB |
Output is correct |
| 2 |
Correct |
178 ms |
239208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
488456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1041 ms |
487028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
508 ms |
389780 KB |
Output is correct |
| 2 |
Correct |
539 ms |
390840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
524 ms |
390804 KB |
Output is correct |
| 2 |
Correct |
529 ms |
387932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
592 ms |
370508 KB |
Output is correct |
| 2 |
Correct |
541 ms |
366976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
492 ms |
368764 KB |
Output is correct |
| 2 |
Execution timed out |
1088 ms |
643924 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
