#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define REI(a,b,c) REP(a,b,c+1)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz size()
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
template<class T> void IN(T& a) {cin>>a;}
template<class T, class... L> void IN(T& a, L&... b) {IN(a); IN(b...);}
template<class T> void OUT(const T& a) {cout<<a;}
template<class T, class... L> void OUT(const T& a, const L&... b) {OUT(a); OUT(b...);}
template<class... T> void OUTL(const T&... a) {OUT(a..., '\n');}
const int MX = 5e6+1e5;
int w, h, n, w1;
ll x[MX], y[MX], a[MX], b[MX];
ll c[MX], d[MX], e[MX], g[MX], v[MX], temp[MX];
int f(int i, int j) {return i+j*w1;}
void rotate() {
// [x,y] => [h-1-y,x]
RE(i,n) {
y[i] = h-1-y[i];
swap(x[i], y[i]);
}
int h1=h+1;
RE(i,w) RE(j,h) temp[h-1-j + i*h1] = v[f(i,j)];
swap(w,h);
w1 = h1;
RE(i,w) RE(j,h) v[f(i,j)] = temp[f(i,j)];
}
void addArea(int bx, int by, int ex, int ey, ll val) {
bx = max(0,bx);
by = max(0,by);
ex = min((int)w,ex+1);
ey = min((int)h,ey+1);
if(bx > ex) return;
if(by > ey) return;
c[f(bx,by)] += val;
c[f(ex,by)] -= val;
c[f(bx,ey)] -= val;
c[f(ex,ey)] += val;
}
void add(int x, int y, ll del) {
if(x >= w || y >= h) return;
if(x < 0 && y < 0) {
int add = min(-x, -y);
x += add;
y += add;
c[0] += del*add;
}
if(x < 0) {
g[f(0,y)] += del;
g[f(0,y-x)] -= del;
y -= x;
x = 0;
}
if(y < 0) {
d[f(x,0)] += del;
d[f(x-y,0)] -= del;
x -= y;
y = 0;
}
e[f(x,y)] += del;
}
void solve() {
RE(i,n) {
ll r = (a[i]-1)/b[i];
add(x[i]-r, y[i]-r, b[i]);
add(x[i]+r+1, y[i]+r+1, -b[i]);
addArea(x[i]+r+1,y[i]+r+1,w,h,-ll(r*2+1)*b[i]);
addArea(x[i]-r,y[i]+r+1,x[i]+r,h,-ll(r*2+2)*b[i]);
}
RE(i,w) RE(j,h) {
int idx = f(i,j);
int idxl = f(i-1,j);
int idxu = f(i,j-1);
int idxul = f(i-1,j-1);
d[idx] += (i ? d[idxl] : 0ll);
g[idx] += (j ? g[idxu] : 0ll);
e[idx] += (i&&j ? e[idxul] : 0ll);
c[idx] += d[idx]+e[idx]+g[idx];
if(i) c[idx] += c[idxl];
if(j) c[idx] += c[idxu];
if(i&&j) c[idx] -= c[idxul];
v[idx] += c[idx];
c[idxul]=d[idxul]=e[idxul]=g[idxul]=0;
if(i == w-1) c[idxu]=d[idxu]=e[idxu]=g[idxu]=0;
if(j == h-1) c[idxl]=d[idxl]=e[idxl]=g[idxl]=0;
if(i == w-1 && j == h-1) c[idx]=d[idx]=e[idx]=g[idx]=0;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// input
IN(w,h,n); w1 = w+1;
RE(i,n) IN(x[i],y[i],a[i],b[i]), x[i]--, y[i]--;
RE(i,4) {
solve();
rotate();
}
RE(i,n) {
ll r = (a[i]-1)/b[i];
addArea(x[i]-r, y[i]-r, x[i]+r, y[i]+r, (-b[i]*r+a[i])*2ll -ll(r*2+4)*b[i]);
}
RE(i,w) RE(j,h) {
if(i) c[f(i,j)] += c[f(i-1,j)];
if(j) c[f(i,j)] += c[f(i,j-1)];
if(i&&j) c[f(i,j)] -= c[f(i-1,j-1)];
v[f(i,j)] += c[f(i,j)];
}
RE(i,w) RE(j,h) v[f(i,j)] >>= 1;
// create sums
REV(i,0,w) REV(j,0,h) v[f(i+1,j+1)] = v[f(i,j)];
RE(i,w) v[f(i,0)]=0;
RE(i,h) v[f(0,i)]=0;
RE(i,w) RE(j,h) v[f(i+1,j+1)] += v[f(i,j+1)]+v[f(i+1,j)]-v[f(i,j)];
// anser queries
ll q;
IN(q);
RE(i,q) {
ll x1, x2, y1, y2;
IN(x1,y1,x2,y2); x1--; y1--;
ll sm = v[f(x2,y2)] - v[f(x1,y2)] - v[f(x2,y1)] + v[f(x1,y1)];
ll area = abs(x2-x1)*abs(y2-y1);
OUTL((sm+area/2)/area);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
279 ms |
238328 KB |
Output is correct |
| 2 |
Correct |
73 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
77 ms |
2468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
278 ms |
238268 KB |
Output is correct |
| 2 |
Correct |
74 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
942 ms |
118508 KB |
Output is correct |
| 2 |
Correct |
73 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
690 ms |
127748 KB |
Output is correct |
| 2 |
Correct |
74 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
414 ms |
240632 KB |
Output is correct |
| 2 |
Correct |
78 ms |
3192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
249 ms |
128124 KB |
Output is correct |
| 2 |
Correct |
85 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1100 ms |
120184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
240 ms |
89100 KB |
Output is correct |
| 2 |
Correct |
74 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
700 ms |
246948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
577 ms |
247056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
124452 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
124536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
767 ms |
128044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1099 ms |
126340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
