#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
//#pragma GCC target ("avx,tune=native")
//Use above if bruteforcing with lots of small operations. Or just use it anytime, there's no downside. AVX is better slightly
/*
TASK: hidden
LANG: C++11
*/
using namespace std;
typedef long long ll;
typedef pair<int, int> pair2;
typedef pair<int, pair<int, int> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 200013
#define MAXA 2500013
#define INF 1000000000000000000LL
#define mp make_pair
#define add push_back
#define remove pop
/*
Why my alg TLE? because TL too strict
should only be O(w * h) with arrays...
*/
int n;
int w, h, q;
int x[MAXN], y[MAXN];
ll a[MAXN], b[MAXN];
bool swapped;
ll * trees[4][MAXA];
ll * metadelta[MAXA]; //ADDS OVER EACH CELL AFTER AND INCLUDING ITSELF
void update(int i, int j, ll sign) {
if (i < 0 || j < 0) return;
//cout << "Updating " << i << ' ' << j << ' ' << sign << endl;
trees[0][i + 1][j + 1] += sign;
trees[1][i + 1][j + 1] += sign * (i + 1);
trees[2][i + 1][j + 1] += sign * (j + 1);
trees[3][i + 1][j + 1] += sign * (i + 1) * (j + 1);
}
void makeArray(int a) {
for (int i = 1; i <= w; i++) {
for (int j = 1; j <= h; j++) {
trees[a][i][j] += trees[a][i - 1][j] + trees[a][i][j - 1] - trees[a][i - 1][j - 1];
//cout << "array made " << i << ' ' << j << " value " << trees[a][i][j] << endl;
}
}
}
ll getSum(int i, int j) {
if (i < 0 || j < 0) return 0;
ll answer = 0;
answer += trees[3][i + 1][j + 1];
//cout << "Trees 3 query " << i << ' ' << j << " is " << answer << endl;
answer += (i + 1) * (trees[2][w][j + 1] - trees[2][i + 1][j + 1]);
answer += (j + 1) * (trees[1][i + 1][h] - trees[1][i + 1][j + 1]);
answer += (i + 1) * (j + 1) * (trees[0][w][h] - trees[0][w][j + 1] - trees[0][i + 1][h] + trees[0][i + 1][j + 1]);
return answer;
}
ll getSum(int a, int b, int c, int d) {
//a, b is bottom left
//c, d is top right
return getSum(c, d) - getSum(a - 1, d) - getSum(c, b - 1) + getSum(a - 1, b - 1);
}
void updateRect(int a, int b, int c, int d, ll value) {
update(c, d, value); update(a - 1, d, -value); update(c, b - 1, -value); update(a - 1, b - 1, value);
}
//i copy this read in part from koosaga. my own code was too slow
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), stdin);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline int _readInt() {
int c, x, s;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//scanf("%d%d", &w, &h);
//scanf("%d", &n);
w = _readInt(); h = _readInt(); n = _readInt();
//cout << "Wha " << endl;
for (int i = 0; i < n; i++) {
//scanf("%d%d%lld%lld", &x[i], &y[i], &a[i], &b[i]);
x[i] = _readInt(); y[i] = _readInt(); a[i] = _readInt(); b[i] = _readInt();
x[i]--;
y[i]--;
}
if (w > h) {
swap(w, h);
for (int i = 0; i < n; i++) {
swap(x[i], y[i]);
}
swapped = true;
}
for (int a = 0; a < 4; a++) for (int i = 0; i <= w; i++) {
trees[a][i] = new ll[h + 1];
for (int j = 0; j < h + 1; j++) {
trees[a][i][j] = 0;
}
}
for (int i = 0; i <= w; i++) {
metadelta[i] = new ll[h + 1];
for (int j = 0; j < h + 1; j++) {
metadelta[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
ll possible = (a[i] - 1) / b[i];
if (possible == 0) {
metadelta[x[i]][y[i]] += a[i];
if (y[i] + 1 < h) {
//cout << "owie " << endl;
metadelta[x[i]][y[i] + 1] += - 2 * a[i];
if (y[i] + 2 < h) metadelta[x[i]][y[i] + 2] += a[i];
}
continue;
}
int vstart = max(0, (int) (x[i] - possible));
int vend = min(w - 1, (int) (x[i] + possible));
int hstart = max(0, (int) (y[i] - possible));
int hend = min(h - 1, (int) (y[i] + possible));
for (int j = vstart; j <= vend; j++) {
ll initialValue = a[i] - b[i] * max(llabs(x[i] - j), llabs(hstart - y[i]));
metadelta[j][hstart] += initialValue;
if (hstart + 1 < h) {
metadelta[j][hstart + 1] += -initialValue;
{metadelta[j][hstart + 1] += b[i];}
}
//find the places where the delta is subtracted in the middle
ll heightDiff = llabs(x[i] - j);
ll spot1 = max(hstart + 1LL, y[i] - heightDiff + 1);
ll spot2 = min(hend + 1LL, y[i] + heightDiff + 1);
//cout << "row " << j << " spot1, spot2 are " << spot1 << ' ' << spot2 << endl;
if (spot1 >= hstart && spot1 <= hend) metadelta[j][(int) spot1] += -b[i];
if (spot2 >= hstart && spot2 <= hend + 1) metadelta[j][(int) spot2] += -b[i];
ll finalValue = a[i] - b[i] * max(llabs(x[i] - j), llabs(hend - y[i]));
if (hend + 1 < h) {
metadelta[j][hend + 1] += -finalValue;
if (hend + 2 < h) metadelta[j][hend + 2] += finalValue;
metadelta[j][hend + 1] += b[i];
}
}
}
for (int i = 0; i < w; i++) {
ll delta = 0;
ll current = 0;
for (int j = 0; j < h; j++) {
delta += metadelta[i][j];
current += delta;
//cout << current << ' ';
updateRect(i, j, i, j, current);
}
//cout << endl;
}
makeArray(0); makeArray(1); makeArray(2); makeArray(3);
q = _readInt();//scanf("%d", &q);//cin >> q;
for (int i = 0; i < q; i++) {
ll x1, y1, x2, y2;
//scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);//cin >> x1 >> y1 >> x2 >> y2;
x1 = _readInt(); y1 = _readInt(); x2 = _readInt(); y2 = _readInt();
x1--; y1--; x2--; y2--;
if (swapped) {
swap(x1, y1);
swap(x2, y2);
}
//cout << "bounds are " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
ll sum = getSum(x1, y1, x2, y2);
ll cells = (x2 - x1 + 1) * (y2 - y1 + 1);
//cout << "query " << i << " found sum " << sum << " cells " << cells << endl;
ll remainder = sum % cells;
if ((cells % 2 == 0 && remainder >= cells / 2) || (cells % 2 == 1 && remainder > cells / 2)) {
printf("%lld\n", 1 + sum / cells);//cout << 1 + sum / cells << endl;
} else {
printf("%lld\n", sum / cells);//cout << sum / cells << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
299852 KB |
Output is correct |
| 2 |
Correct |
44 ms |
104532 KB |
Output is correct |
| 3 |
Correct |
37 ms |
104532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
299852 KB |
Output is correct |
| 2 |
Correct |
38 ms |
104532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
202380 KB |
Output is correct |
| 2 |
Correct |
42 ms |
104532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
207432 KB |
Output is correct |
| 2 |
Correct |
52 ms |
104532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
299852 KB |
Output is correct |
| 2 |
Correct |
55 ms |
104532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
182692 KB |
Output is correct |
| 2 |
Correct |
55 ms |
104532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
202380 KB |
Output is correct |
| 2 |
Correct |
53 ms |
104532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
163152 KB |
Output is correct |
| 2 |
Correct |
43 ms |
104532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
299852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
299852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
202380 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
202360 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
205332 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
202380 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
