#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define NDEBUG
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
struct bad {
int W,H;
ll dat[2500000];
void init(int _W, int _H) {
W = _W, H = _H;
// F0R(i,2500000) dat[i] = 0;
memset(dat,0,sizeof dat);
}
ll get(int a, int b) {
assert(0 <= a && a < W && 0 <= b && b < H);
return dat[H*a+b];
}
void ad(int a, int b, ll val) {
assert(0 <= a && a < W && 0 <= b && b < H);
dat[H*a+b] += val;
}
};
struct cum {
bad L, up, down;
int W,H;
void init(int _W, int _H) {
W = _W, H = _H;
L.init(W,H), up.init(W,H), down.init(W,H);
}
void prop() {
F0R(i,W) {
F0R(j,H) {
L.ad(i,j,down.get(i,j)+up.get(i,j));
if (i != W-1) {
up.ad(i+1,min(H-1,j+1),up.get(i,j));
if (j) down.ad(i+1,j-1,down.get(i,j));
}
}
}
F0R(i,W) F0Rd(j,H-1) L.ad(i,j,L.get(i,j+1));
}
};
cum c, cX;
bad res;
int W,H,N;
vector<array<int,4>> todo;
pi trans(pi x) {
return {H-1-x.s,x.f};
}
void prin(vector<vl> v) {
F0R(i,sz(v)) {
F0R(j,sz(v[i])) cout << v[i][j] << " ";
cout << "\n";
}
cout << "----\n";
}
void rot() {
bad RES; RES.init(H,W);
F0R(i,W) F0R(j,H) {
pi x = trans({i,j});
RES.ad(x.f,x.s,res.get(i,j));
}
F0R(i,sz(todo)) {
pi x = trans({todo[i][0],todo[i][1]});
todo[i][0] = x.f, todo[i][1] = x.s;
}
//prin(res);
//prin(RES);
swap(res,RES); swap(W,H);
}
void prop() {
c.prop(), cX.prop();
F0R(i,W) F0R(j,H) res.ad(i,j,c.L.get(i,j)+cX.L.get(i,j)*i);
}
void process(array<int,4> a) {
// cout << "TT\n";
assert(0 <= a[0] && a[0] < W && 0 <= a[1] && a[1] < H);
int mul = a[2]/a[3];
ll z = a[2]+(ll)a[0]*a[3];
if (a[0]+1 < W) {
c.up.ad(a[0]+1,a[1],z);
cX.up.ad(a[0]+1,a[1],-a[3]);
}
if (a[0]+mul+1 < W) {
c.up.ad(a[0]+1+mul,min(a[1]+mul,H-1),-z);
cX.up.ad(a[0]+1+mul,min(a[1]+mul,H-1),a[3]);
}
if (a[0]+1 < W && a[1]-2 >= 0) {
c.down.ad(a[0]+1,a[1]-2,-z);
cX.down.ad(a[0]+1,a[1]-2,a[3]);
}
if (a[0]+1+mul < W && a[1]-2-mul >= 0) {
c.down.ad(a[0]+1+mul,a[1]-2-mul,z);
cX.down.ad(a[0]+1+mul,a[1]-2-mul,-a[3]);
}
}
void solve() {
c.init(W,H), cX.init(W,H);
for (auto a: todo) process(a);
prop();
}
ll query(int x1, int x2, int y1, int y2) {
x1 --, x2 --, y1 --, y2 --;
ll ret = res.get(x2,y2);
if (x1) {
ret -= res.get(x1-1,y2);
if (y1) ret += res.get(x1-1,y1-1);
}
if (y1) ret -= res.get(x2,y1-1);
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> W >> H >> N;
res.init(W,H);
F0R(i,N) {
//int x = rand() % W+1,y = rand() % H+1,a = rand() % 500+1,b = rand() % 50+1;
int x,y,a,b; cin >> x >> y >> a >> b;
x--, y--;
res.ad(x,y,a);
todo.pb({x,y,a,b});
}
F0R(i,4) {
solve();
rot();
}
/*F0R(i,W) {
F0R(j,H) cout << res[i][j] << " ";
cout << "\n";
}
exit(0);*/
F0R(i,W) F0R(j,H) {
// cout << i << " " << j << " " << res.get(i,j) << "\n";
if (i) {
res.ad(i,j,res.get(i-1,j));
if (j) res.ad(i,j,-res.get(i-1,j-1));
}
if (j) res.ad(i,j,res.get(i,j-1));
}
int Q; cin >> Q;
F0R(i,Q) {
int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
cout << (ll)round((ld)query(x1,x2,y1,y2)/(x2-x1+1)/(y2-y1+1)) << "\n";
}
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
524 ms |
156792 KB |
Output is correct |
| 2 |
Correct |
324 ms |
161380 KB |
Output is correct |
| 3 |
Correct |
338 ms |
162544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
455 ms |
162544 KB |
Output is correct |
| 2 |
Correct |
343 ms |
165100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
604 ms |
165100 KB |
Output is correct |
| 2 |
Correct |
315 ms |
165100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
647 ms |
165100 KB |
Output is correct |
| 2 |
Correct |
369 ms |
165100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
690 ms |
165100 KB |
Output is correct |
| 2 |
Correct |
366 ms |
167724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
504 ms |
167724 KB |
Output is correct |
| 2 |
Correct |
378 ms |
167724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
792 ms |
167724 KB |
Output is correct |
| 2 |
Correct |
423 ms |
167724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
504 ms |
167724 KB |
Output is correct |
| 2 |
Correct |
315 ms |
167724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
955 ms |
174336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
942 ms |
175128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
175128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
175128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1004 ms |
175140 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
984 ms |
175240 KB |
Output is correct |
| 2 |
Correct |
750 ms |
182492 KB |
Output is correct |
