#include "bits/stdc++.h"
using namespace std;
vector <vector <long long>> a, tbm, tbc, rowm, rowc, colm, colc, P, Q, D;
int w, h;
bool inside(int x, int y) {
return (0 <= x && x < w) && (0 <= y && y < h);
}
void addTB(int i, int j, long long x, long long d, int signx, int signy) {
int len = (x / d);
int doable = min(signx == -1 ? i : w - i - 1, signy == -1 ? j : h - j - 1);
tbm[i][j] += -signx * d;
tbc[i][j] += x + signx * d * i;
if(inside(i + signx * len + signx, j + signy * len + signy)) {
tbm[i + signx * len + signx][j + signy * len + signy] -= -signx * d;
tbc[i + signx * len + signx][j + signy * len + signy] -= x + signx * d * i;
}
if(inside(i, j - signy)){
rowm[i][j - signy] += -signx * d;
rowc[i][j - signy] += x + signx * d * i;
if(inside(i + signx * len + signx, j - signy)) {
rowm[i + signx * len + signx][j - signy] -= -signx * d;
rowc[i + signx * len + signx][j - signy] -= x + signx * d * i;
}
}
if(inside(i - signx, j)) {
colm[i - signx][j] += -signy * d;
colc[i - signx][j] += x + signy * d * j;
if(inside(i - signx, j + signy * len + signy)) {
colm[i - signx][j + signy * len + signy] -= -signy * d;
colc[i - signx][j + signy * len + signy] -= x + signy * d * j;
}
}
if(doable < len) {
int ex = i + signx * len;
int ey = j + signy * len;
if(ex < 0) ex = 0;
if(ex >= w) ex = w-1;
if(ey < 0) ey = 0;
if(ey >= h) ey = h-1;
int fx = i + signx * doable;
int fy = j + signy * doable;
long long nx = x - (doable + 1) * d;
if(ey == fy) {
if(inside(fx + signx, fy)) {
rowm[fx + signx][fy] -= -signx * d;
rowc[fx + signx][fy] -= nx + signx * d * (fx + signx);
}
if(inside(ex + signx, ey)) {
rowm[ex + signx][ey] += -signx * d;
rowc[ex + signx][ey] += nx + signx * d * (fx + signx);
}
} else {
if(inside(fx, fy + signy)) {
colm[fx][fy + signy] -= -signy * d;
colc[fx][fy + signy] -= nx + signy * d * (fy + signy);
}
if(inside(ex, ey + signy)) {
colm[ex][ey + signy] += -signy * d;
colc[ex][ey + signy] += nx + signy * d * (fy + signy);
}
}
}
}
void reset(vector <vector<long long>> &v) {
for(auto &i : v) {
for(auto &j : i) {
j = 0;
}
}
}
void init(vector <vector <long long>> &v) {
v.resize(w);
for(auto &i : v) {
i.resize(h);
}
}
int value(int x, int y) {
return inside(x, y) ? a[x][y] : 0;
}
long long query(int x, int y, int p, int q) {
long long ans = 0;
ans += value(p, q);
ans -= value(p, y-1);
ans -= value(x-1, q);
ans += value(x-1, y-1);
return ans;
}
int main(int argc, char const *argv[])
{
scanf("%d %d", &w, &h);
swap(w, h);
init(tbm);
init(tbc);
init(rowm);
init(rowc);
init(colm);
init(colc);
init(P);
init(Q);
init(D);
init(a);
int n;
scanf("%d", &n);
vector <pair <int, int>> u, v;
for(int i = 0; i < n; i++) {
int x, y, p, q;
scanf("%d %d %d %d", &x, &y, &p, &q);
swap(x, y);
u.emplace_back(x-1, y-1);
v.emplace_back(p, q);
}
for(int signx : {-1, 1}) {
for(int signy : {-1, 1}) {
reset(tbm);
reset(tbc);
reset(rowm);
reset(rowc);
reset(colm);
reset(colc);
reset(P);
reset(Q);
reset(D);
for(int i = 0; i < n; i++) {
addTB(u[i].first, u[i].second, v[i].first, v[i].second, signx, signy);
}
for(int i = w-1; i >= 0; i--) {
long long sum_m = 0;
long long sum_c = 0;
if(signy == -1) {
for(int j = h-1; j >= 0; j--) {
sum_m += colm[i][j];
sum_c += colc[i][j];
Q[i][j] = sum_m * j + sum_c;
}
} else {
for(int j = 0; j < h; j++) {
sum_m += colm[i][j];
sum_c += colc[i][j];
Q[i][j] = sum_m * j + sum_c;
}
}
}
for(int j = h-1; j >= 0; j--) {
long long sum_m = 0;
long long sum_c = 0;
if(signx == -1) {
for(int i = w-1; i >= 0; i--) {
sum_m += rowm[i][j];
sum_c += rowc[i][j];
P[i][j] = sum_m * i + sum_c;
}
} else {
for(int i = 0; i < w; i++) {
sum_m += rowm[i][j];
sum_c += rowc[i][j];
P[i][j] = sum_m * i + sum_c;
}
}
}
for(int j = 0; j < h; j++) {
int x = signx == -1 ? w-1 : 0;
int y = j;
long long sum_m = 0;
long long sum_c = 0;
while(inside(x, y)) {
sum_m += tbm[x][y];
sum_c += tbc[x][y];
D[x][y] = sum_m * x + sum_c;
x += signx;
y += signy;
}
}
for(int i = 0; i < w; i++) {
int x = i;
int y = signy == -1 ? h-1 : 0;
long long sum_m = 0;
long long sum_c = 0;
while(inside(x, y)) {
sum_m += tbm[x][y];
sum_c += tbc[x][y];
D[x][y] = sum_m * x + sum_c;
x += signx;
y += signy;
}
}
for(int i = 0; i < w; i++) {
long long sum = 0;
if(signy == -1) {
for(int j = 0; j < h; j++) {
sum += D[i][j];
sum -= P[i][j];
a[i][j] += sum;
}
} else {
for(int j = h-1; j >= 0; j--) {
sum += D[i][j];
sum -= P[i][j];
a[i][j] += sum;
}
}
}
for(int j = 0; j < h; j++) {
long long sum = 0;
if(signx == -1) {
for(int i = 0; i < w; i++) {
sum += D[i][j];
sum -= Q[i][j];
a[i][j] += sum;
}
} else {
for(int i = w-1; i >= 0; i--) {
sum += D[i][j];
sum -= Q[i][j];
a[i][j] += sum;
}
}
}
for(int i = 0; i < w; i++) {
for(int j = 0; j < h; j++) {
a[i][j] -= D[i][j];
}
}
// break;
}
// break;
}
reset(rowc);
reset(rowm);
reset(colc);
reset(colm);
for(int i = 0; i < n; i++) {
int x = u[i].first;
int y = u[i].second;
int p = v[i].first;
int q = v[i].second;
rowm[min(w-1, x + (p / q))][y] += -q;
rowc[min(w-1, x + (p / q))][y] += p + q * x;
if(inside(x-1, y)) {
rowm[x-1][y] -= -q;
rowc[x-1][y] -= p + q * x;
}
rowm[x][y] += q;
rowc[x][y] += p - q * x;
if(inside(x - (p / q) - 1, y)) {
rowm[x - (p / q) - 1][y] -= q;
rowc[x - (p / q) - 1][y] -= p - q * x;
}
colm[x][min(h-1, y + (p / q))] += -q;
colc[x][min(h-1, y + (p / q))] += p + q * y;
if(inside(x, y-1)) {
colm[x][y-1] -= -q;
colc[x][y-1] -= p + q * y;
}
colm[x][y] += q;
colc[x][y] += p - q * y;
if(inside(x, y - (p / q) - 1)) {
colm[x][y - (p / q) - 1] -= q;
colc[x][y - (p / q) - 1] -= p - q * y;
}
a[x][y] += p;
}
for(int j = 0; j < h; j++) {
long long sum_c = 0;
long long sum_m = 0;
for(int i = w-1; i >= 0; i--) {
sum_m += rowm[i][j];
sum_c += rowc[i][j];
P[i][j] = sum_m * i + sum_c;
}
}
for(int i = 0; i < w; i++) {
long long sum_c = 0;
long long sum_m = 0;
for(int j = h-1; j >= 0; j--) {
sum_m += colm[i][j];
sum_c += colc[i][j];
Q[i][j] = sum_m * j + sum_c;
}
}
for(int i = 0; i < w; i++) {
for(int j = 0; j < h; j++) {
a[i][j] -= P[i][j] + Q[i][j];
}
}
for(int i = 0; i < w; i++) {
for(int j = 0; j < h; j++) {
a[i][j] += value(i - 1, j);
a[i][j] += value(i, j - 1);
a[i][j] -= value(i - 1, j - 1);
}
}
int Q;
scanf("%d", &Q);
for(int i = 0; i < Q; i++) {
int x, y, p, q;
scanf("%d %d %d %d", &x, &y, &p, &q);
swap(x, y);
swap(p, q);
long long sum = query(x-1, y-1, p-1, q-1);
double tot = (p - x + 1) * (q - y + 1);
long long res = (sum / tot) + 0.5;
printf("%lld\n", res);
}
return 0;
}
Compilation message
nuclearia.cpp: In function 'int main(int, const char**)':
nuclearia.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &w, &h);
~~~~~^~~~~~~~~~~~~~~~~
nuclearia.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
nuclearia.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &x, &y, &p, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:309:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
nuclearia.cpp:312:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &x, &y, &p, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
547 ms |
196252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
532 ms |
196272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
196512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1095 ms |
245324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
871 ms |
245324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
440 ms |
245324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
245324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
446 ms |
245324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
245324 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
245324 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
245324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
245324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
245324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1100 ms |
245324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
