#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 yk[MAXN], yb[MAXN];
//vector<vl> yk[2], yb[2], xk[2], xb[2];
vector<pair<int, ll>> xk[MAXN][2], xb[MAXN][2];
vector<pair<int, ll>> yk[MAXN][2], yb[MAXN][2];
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);
}
void addPlant (ll x, ll y, ll a, ll b) {
int mxd = getmxD(a, b);
int istr0 = h+y-x;
int istr1 = x+y;
/// x
int frx = max((ll)1, x-mxd);
int tox = min((ll)h, x+mxd);
/// [frx; x]
xb[frx][0].pb({istr0, a-b*x});
xk[frx][0].pb({istr0, b});
xb[frx][1].pb({istr1+1, -a + b*x});
xk[frx][1].pb({istr1+1, -b});
xb[x+1][0].pb({istr0, -a+b*x});
xk[x+1][0].pb({istr0, -b});
xb[x+1][1].pb({istr1+1, a - b*x});
xk[x+1][1].pb({istr1+1, b});
/// (x; tox]
xb[x+1][1].pb({istr1, a+b*x});
xk[x+1][1].pb({istr1, -b});
xb[x+1][0].pb({istr0+1, -a-b*x});
xk[x+1][0].pb({istr0+1, b});
xb[tox+1][1].pb({istr1, -a-b*x});
xk[tox+1][1].pb({istr1, +b});
xb[tox+1][0].pb({istr0+1, a+b*x});
xk[tox+1][0].pb({istr0+1, -b});
/// y
istr0 = w+x-y;
int fry = max((ll)1, y-mxd);
int toy = min((ll)w, y+mxd);
//cout << " istr0 " << istr0 << " istr1 = " << istr1 << " fry = " << fry << " toy=" << toy << endl;
/// [y-mxd; y)
yb[fry][0].pb({istr0+1, a-b*y});
yk[fry][0].pb({istr0+1, b});
yb[fry][1].pb({istr1, -a+b*y});
yk[fry][1].pb({istr1, -b});
yb[y][0].pb({istr0+1, -a+b*y});
yk[y][0].pb({istr0+1, -b});
yb[y][1].pb({istr1, a-b*y});
yk[y][1].pb({istr1, b});
/// (y; toy]
yb[y+1][1].pb({istr1+1, a+b*y});
yk[y+1][1].pb({istr1+1, -b});
yb[y+1][0].pb({istr0, -a-b*y});
yk[y+1][0].pb({istr0, b});
yb[toy+1][1].pb({istr1+1, -a-b*y});
yk[toy+1][1].pb({istr1+1, b});
yb[toy+1][0].pb({istr0, a+b*y});
yk[toy+1][0].pb({istr0, -b});
}
//ll prefb[2][MAXN], prefk[2][MAXN]; /// prefixes for diagonals
//ll sb[2][MAXN], sk[2][MAXN];
ll fen[2][2][MAXN];
void upd (int id1, int id2, int p, ll x) {
for (int i = p; i < MAXN; i += i&(-i))
fen[id1][id2][i] += x;
}
ll get (int id1, int id2, int p) {
ll ret = 0;
for (int i = p; i > 0; i -= i&(-i))
ret += fen[id1][id2][i];
return ret;
}
ll get(int id1, int id2, int fr, int to) {
return get(id1, id2, to) - get(id1, id2, fr-1);
}
void calcGrid () {
/// x
//FOR(i, 0, w+h+5) FOR(k, 0, 1) prefb[k][i]= prefk[k][i] = 0;
//FOR(i, 0, w+h+5) FOR(id1, 0, 1) FOR(id2, 0, 1) fen[id1][id2][i] = 0;
FOR(x, 1, h) {
//cout << " x = " << x << endl;
//ll sb = 0, sk = 0;
FOR(k, 0, 1) {
for (auto p : xb[x][k]) {
int id = p.f;
ll val = p.s;
//prefb[k][id] += val;
upd(0, k, id, val);
}
for (auto p : xk[x][k]) {
int id = p.f;
ll val = p.s;
//prefk[k][id] += val;
upd(1, k, id, val);
}
}
/* FOR(istr, 0, w+h+5) {
//cout << " istr = " << istr << endl;
FOR(k, 0, 1) {
sb[k][istr] = sk[k][istr] = 0;
if (istr > 0) sb[k][istr] += sb[k][istr-1];
if (istr > 0) sk[k][istr] += sk[k][istr-1];
sb[k][istr] += prefb[k][istr];
sk[k][istr] += prefk[k][istr];
// cout << " k = " << k << endl;
// cout << " prefk = " << prefk[k][istr] << " prefb = " << prefb[k][istr] << endl;
// cout << " sk = " << sk[k][istr] << " sb = " << sb[k][istr] << endl;
}
}*/
FOR(y, 1, w) {
int istr0 = h+y-x;
int istr1 = x+y;
//ll cur0 = sb[0][istr0] + sk[0][istr0] * x;
//ll cur1 = sb[1][istr1] + sk[1][istr1] * x;
ll cur0 = get(0, 0, istr0) + get(1, 0, istr0) * x;
ll cur1 = get(0, 1, istr1) + get(1, 1, istr1) * x;
// cout << " x = " << x << " y = " << y << " cur0 = " << cur0 << " cur1 = " << cur1 << endl;
grid[x][y] += cur0 + cur1;
}
}
/// y
//FOR(i, 0, w+h+5) FOR(k, 0, 1) prefb[k][i]= prefk[k][i] = 0;
FOR(i, 0, w+h+5) FOR(id1, 0, 1) FOR(id2, 0, 1) fen[id1][id2][i] = 0;
FOR(y, 1, w) {
// cout << " y = " << y << endl;
//ll sb = 0, sk = 0;
FOR(k, 0, 1) {
for (auto p : yb[y][k]) {
int id = p.f;
ll val = p.s;
//prefb[k][id] += val;
upd(0, k, id, val);
}
for (auto p : yk[y][k]) {
int id = p.f;
ll val = p.s;
//prefk[k][id] += val;
upd(1, k, id, val);
}
}
/*FOR(istr, 0, w+h+5) {
//cout << " istr = " << istr << endl;
FOR(k, 0, 1) {
sb[k][istr] = sk[k][istr] = 0;
if (istr > 0) sb[k][istr] += sb[k][istr-1];
if (istr > 0) sk[k][istr] += sk[k][istr-1];
sb[k][istr] += prefb[k][istr];
sk[k][istr] += prefk[k][istr];
//cout << " k = " << k << endl;
//cout << " prefk = " << prefk[k][istr] << " prefb = " << prefb[k][istr] << endl;
//cout << " sk = " << sk[k][istr] << " sb = " << sb[k][istr] << endl;
}
}*/
FOR(x, 1, h) {
int istr0 = w+x-y;
int istr1 = x+y;
//ll cur0 = sb[0][istr0] + sk[0][istr0] * y;
//ll cur1 = sb[1][istr1] + sk[1][istr1] * y;
ll cur0 = get(0, 0, istr0) + get(1, 0, istr0) * y;
ll cur1 = get(0, 1, istr1) + get(1, 1, istr1) * y;
// cout << " x = " << x << " y = " << y << " cur0 = " << cur0 << " cur1 = " << cur1 << endl;
grid[x][y] += cur0 + cur1;
}
}
}
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);
// sb.pb(tmp);
// sk.pb(tmp);
//FOR(k, 0, 1) {
// yb[k].pb(tmp);
// yk[k].pb(tmp);
//xb[k].pb(tmp);
//xk[k].pb(tmp);
//}
}
/*tmp.clear();
REP(2*h+5) tmp.pb(0);
REP(2*w+5) {
//grid.pb(tmp);
//pref.pb(tmp);
FOR(k, 0, 1) {
//yb[k].pb(tmp);
//yk[k].pb(tmp);
xb[k].pb(tmp);
xk[k].pb(tmp);
}
}*/
cin >> n;
REP(n) {
int x, y;
ll a, b;
cin >> x >> y >> a >> b;
swap(x, y);
addPlant (x, y, a, b);
}
//cout << " asdas" << endl;
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 >> x1 >> y11 >> x2 >> y2;
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
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
610 ms |
646268 KB |
Output is correct |
| 2 |
Correct |
299 ms |
474736 KB |
Output is correct |
| 3 |
Correct |
314 ms |
473860 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
590 ms |
646264 KB |
Output is correct |
| 2 |
Correct |
401 ms |
474740 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
384 ms |
509840 KB |
Output is correct |
| 2 |
Correct |
369 ms |
473932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
515 ms |
523096 KB |
Output is correct |
| 2 |
Correct |
300 ms |
474808 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
747 ms |
652148 KB |
Output is correct |
| 2 |
Correct |
325 ms |
476008 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
508 ms |
546608 KB |
Output is correct |
| 2 |
Correct |
320 ms |
474736 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
543 ms |
513440 KB |
Output is correct |
| 2 |
Correct |
305 ms |
474700 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
462 ms |
519060 KB |
Output is correct |
| 2 |
Correct |
297 ms |
474476 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1139 ms |
802940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1113 ms |
799924 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1120 ms |
661976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1100 ms |
666652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1123 ms |
638268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1053 ms |
633080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
