//#define DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
const int MAXN = 2e5+5;
int W,H,N,Q;
bool flag;
struct Plant { int x, y, a, b; };
struct Data { ll ldmx, ldmy, ldc, rdmx, rdmy, rdc, rmx, rmy, rc, cmx, cmy, cc, v; };
#ifdef DEBUG
#define DBG(...) __VA_ARGS__
#else
#define DBG(...)
#endif
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> W >> H;
cin >> N; Plant plant[N]; FOR(i,0,N-1) { int x,y,a,b; cin >> x >> y >> a >> b; plant[i] = {x,y,a,b}; }
Data g[W+2][H+2]; memset(g, 0, sizeof g);
for (Plant p : plant) {
int r = (p.a+p.b-1)/p.b - 1;
// i: [1 to r] :: [y-r, y-i-1], [y-i,y+i], [y+i+1,y+r]
//p.a - (p.y-y)*p.b
//= y*p.b - p.y*p.b + p.a
// u
g[max(1,p.x-r)][max(1,p.y-r)].rmy += p.b;
g[max(1,p.x-r)][max(1,p.y-r)].rc += - p.y*p.b + p.a;
g[min(W,p.x+r)+1][max(1,p.y-r)].rmy -= p.b;
g[min(W,p.x+r)+1][max(1,p.y-r)].rc -= - p.y*p.b + p.a;
//p.a - (y-p.y)*p.b
//= y*(-p.b) + p.y*p.b + p.a
// d
g[max(1,p.x-r)][min(H,p.y+r)+1].rmy -= - p.b;
g[max(1,p.x-r)][min(H,p.y+r)+1].rc -= p.y*p.b + p.a;
g[min(W,p.x+r)+1][min(H,p.y+r)+1].rmy += - p.b;
g[min(W,p.x+r)+1][min(H,p.y+r)+1].rc += p.y*p.b + p.a;
int x,y;
//p.a - (p.x-x)*p.b
//= x*p.b - p.x*p.b + p.a
// ld
x = p.x-r, y = p.y-r;
if (x < 1 or y < 1) {
int z = max(1-x, 1-y);
int xp = x+z, yp = y+z;
g[max(1,x)][yp].rmy -= p.b;
g[max(1,x)][yp].rc -= - p.y*p.b + p.a;
g[xp][yp].rmy += p.b;
g[xp][yp].rc += - p.y*p.b + p.a;
g[max(1,x)][yp].rmx += p.b;
g[max(1,x)][yp].rc += - p.x*p.b + p.a;
g[xp][yp].rmx -= p.b;
g[xp][yp].rc -= - p.x*p.b + p.a;
x = xp, y = yp;
}
g[x][y].ldmy -= p.b;
g[x][y].ldc -= - p.y*p.b + p.a;
g[p.x][p.y].ldmy += p.b;
g[p.x][p.y].ldc += - p.y*p.b + p.a;
g[x][y].ldmx += p.b;
g[x][y].ldc += - p.x*p.b + p.a;
g[p.x][p.y].ldmx -= p.b;
g[p.x][p.y].ldc -= - p.x*p.b + p.a;
//
g[p.x][p.y].ldmy += - p.b;
g[p.x][p.y].ldc += p.y*p.b + p.a;
g[p.x][p.y].ldmx -= - p.b;
g[p.x][p.y].ldc -= p.x*p.b + p.a;
x = p.x+r, y = p.y+r;
if (x > W or y > H) {
int z = max(x-W, y-H);
int xp = x-z, yp = y-z;
g[xp+1][yp].rmy += - p.b;
g[xp+1][yp].rc += p.y*p.b + p.a;
g[min(W,x)+1][yp].rmy -= - p.b;
g[min(W,x)+1][yp].rc -= p.y*p.b + p.a;
g[xp][yp].rmx -= - p.b;
g[xp][yp].rc -= p.x*p.b + p.a;
g[min(W,x)+1][yp].rmx += - p.b;
g[min(W,x)+1][yp].rc += p.x*p.b + p.a;
x = xp, y = yp;
}
g[x+1][y+1].ldmy -= - p.b;
g[x+1][y+1].ldc -= p.y*p.b + p.a;
g[x+1][y+1].ldmx += - p.b;
g[x+1][y+1].ldc += p.x*p.b + p.a;
// rd
x = p.x-r, y = p.y+r;
DBG(cout << "UPDATE " << x << " " << y << " TO " << p.x << " " << p.y << endl;)
if (x < 1 or y > H) {
int z = max(1-x, y-H);
int xp = x+z, yp = y-z;
DBG(cout << " CONVERT X Y TO P " << xp << " " << yp << endl;)
g[max(1,x)][yp].rmy += - p.b;
g[max(1,x)][yp].rc += p.y*p.b + p.a;
g[xp][yp].rmy -= - p.b;
g[xp][yp].rc -= p.y*p.b + p.a;
g[max(1,x)][yp].rmx -= p.b;
g[max(1,x)][yp].rc -= - p.x*p.b + p.a;
g[xp][yp].rmx += p.b;
g[xp][yp].rc += - p.x*p.b + p.a;
x = xp, y = yp;
}
g[x][y].rdmy += - p.b;
g[x][y].rdc += p.y*p.b + p.a;
g[p.x][p.y].rdmy -= - p.b;
g[p.x][p.y].rdc -= p.y*p.b + p.a;
g[x][y].rdmx -= p.b;
g[x][y].rdc -= - p.x*p.b + p.a;
g[p.x][p.y].rdmx += p.b;
g[p.x][p.y].rdc += - p.x*p.b + p.a;
//
g[p.x][p.y].rdmy -= p.b;
g[p.x][p.y].rdc -= - p.y*p.b + p.a;
g[p.x][p.y].rdmx += - p.b;
g[p.x][p.y].rdc += p.x*p.b + p.a;
x = p.x+r, y = p.y-r;
DBG(cout << "UPDATE " << p.x << " " << p.y << " TO " << x << " " << y << endl;)
if (x > W or y < 1) {
int z = max(x-W, 1-y);
int xp = x-z, yp = y+z;
DBG(cout << " CONVERT X Y TO P " << xp << " " << yp << endl;)
DBG(cout << " RANGE " << xp+1 << " TO " << min(W,x)+1 << " AT " << yp << endl;)
g[xp+1][yp].rmy -= p.b;
g[xp+1][yp].rc -= - p.y*p.b + p.a;
g[min(W,x)+1][yp].rmy += p.b;
g[min(W,x)+1][yp].rc += - p.y*p.b + p.a;
g[xp+1][yp].rmx += - p.b;
g[xp+1][yp].rc += p.x*p.b + p.a;
g[min(W,x)+1][yp].rmx -= - p.b;
g[min(W,x)+1][yp].rc -= p.x*p.b + p.a;
x = xp, y = yp;
}
DBG(cout << " MAIN " << x+1 << " " << y-1 << endl;)
g[x+1][y-1].rdmy += p.b;
g[x+1][y-1].rdc += - p.y*p.b + p.a;
g[x+1][y-1].rdmx -= - p.b;
g[x+1][y-1].rdc -= p.x*p.b + p.a;
//break;
}
FOR(x,1,W) FOR(y,1,H) {
g[x][y].rmx += g[x-1][y].rmx;
g[x][y].rmy += g[x-1][y].rmy;
g[x][y].rc += g[x-1][y].rc;
g[x][y].ldmx += g[x-1][y-1].ldmx;
g[x][y].ldmy += g[x-1][y-1].ldmy;
g[x][y].ldc += g[x-1][y-1].ldc;
g[x][y].rdmx += g[x-1][y+1].rdmx;
g[x][y].rdmy += g[x-1][y+1].rdmy;
g[x][y].rdc += g[x-1][y+1].rdc;
g[x][y].cmx = g[x][y-1].cmx + g[x][y].ldmx + g[x][y].rdmx + g[x][y].rmx;
g[x][y].cmy = g[x][y-1].cmy + g[x][y].ldmy + g[x][y].rdmy + g[x][y].rmy;
g[x][y].cc = g[x][y-1].cc + g[x][y].ldc + g[x][y].rdc + g[x][y].rc;
g[x][y].v = g[x][y].cmx * x + g[x][y].cmy * y + g[x][y].cc;
g[x][y].v += g[x-1][y].v + g[x][y-1].v - g[x-1][y-1].v;
}
DBG(
cout << "END " << endl;
//FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].rmx << ' '; } cout << endl; } cout << endl;
//FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].rmy << ' '; } cout << endl; } cout << endl;
//FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].rc << ' '; } cout << endl; } cout << endl;
//FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].cmx << ' '; } cout << endl; } cout << endl;
///FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].cmy << ' '; } cout << endl; } cout << endl;
///FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].cc << ' '; } cout << endl; } cout << endl;
cout << "V " << endl;
FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].v << ' '; } cout << endl; } cout << endl;
)
cin >> Q; FOR(q,0,Q-1) {
int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
ll s = g[x2][y2].v - g[x1-1][y2].v + g[x1-1][y1-1].v - g[x2][y1-1].v;
ll r = (ll)(x2-x1+1)*(y2-y1+1);
DBG(cout << "S R " << s << " " << r << endl;)
cout << (ll)round((long double)s/r) << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
764 ms |
763816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
748 ms |
763608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
259 ms |
255904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
298 ms |
280156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
930 ms |
769596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
457 ms |
311440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
413 ms |
261732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
344 ms |
209784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1052 ms |
776692 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1107 ms |
776712 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
540 ms |
268576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
546 ms |
268112 KB |
Output is correct |
| 2 |
Incorrect |
546 ms |
268636 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
551 ms |
271364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
556 ms |
268460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
