| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 886876 |
2023-12-13T06:06:23 Z |
awu |
Nuclearia (CEOI15_nuclearia) |
C++14 |
|
687 ms |
380496 KB |
#include <bits/stdc++.h>
using namespace std;
int main() {
int w, h, n;
cin >> w >> h >> n;
vector<vector<long long>> grid(h + 3, vector<long long>(w + 3, 0));
vector<vector<long long>> ps(h + 1, vector<long long>(w + 1, 0));
if (h == 1) {
vector<int> dgrid(w + 2, 0);
vector<int> ddgrid(w + 3, 0);
while (n--) {
int x, y;
long long a, b;
cin >> x >> y >> a >> b;
int rad = ceil((double) a / b) - 1;
int v1 = a - b * rad;
int v2 = b - v1;
if (x - rad < 1) {
ddgrid[1] += v1 + (1 - x + rad) * b;
ddgrid[2] += v2 - (1 - x + rad) * b;
} else {
ddgrid[x - rad] += v1;
ddgrid[x - rad + 1] += v2;
}
ddgrid[x + 1] -= b * 2;
if (x + rad <= w) {
ddgrid[x + rad + 1] += v2;
ddgrid[x + rad + 2] += v1;
}
}
for (int x = 1; x <= w; ++x) {
dgrid[x] = dgrid[x - 1] + ddgrid[x];
grid[1][x] = grid[1][x - 1] + dgrid[x];
}
} else if ((long long) w * h * n <= 1e8) {
while (n--) {
int x, y;
long long a, b;
cin >> x >> y >> a >> b;
for (int r = 1; r <= h; ++r) {
for (int c = 1; c <= w; ++c) {
if (b * max(abs(x - c), abs(y - r)) < a) {
grid[r][c] += a - b * max(abs(x - c), abs(y - r));
}
}
}
}
} else {
vector<vector<long long>> dgrid(h + 3, vector<long long>(w + 3, 0)), ddgrid(h + 3, vector<long long>(w + 3, 0)), dddiag1grid(h + 3, vector<long long>(w + 3, 0)), dddiag2grid(h + 3, vector<long long>(w + 3, 0));
vector<vector<long long>> dddvert(h + 3, vector<long long>(w + 3, 0)), ddddiag1(w + h + 7, vector<long long>(min(w, h) + 3, 0)), ddddiag2(w + h + 7, vector<long long>(min(w, h) + 3, 0));
while (n--) {
int x, y, a, b;
cin >> x >> y >> a >> b;
if (b >= a) {
grid[y][x] += a;
continue;
}
int rad = ceil((double) a / b) - 1;
int v1 = a - b * rad;
int v2 = b - v1;
// vert lines
dddvert[y - rad][x - rad] += v1;
dddvert[y + rad + 1][x - rad] -= v1;
dddvert[y - rad][x - rad + 1] += v2;
dddvert[y + rad + 1][x - rad + 1] -= v2;
dddvert[y - rad][x + rad + 2] += v1;
dddvert[y + rad + 1][x + rad + 2] -= v1;
dddvert[y - rad][x + rad + 1] += v2;
dddvert[y + rad + 1][x + rad + 1] -= v2;
x++;
// diag1 lines
int d = x - y + h + 3 - 1;
int i = x - max(0, d - min(h, w) - 3 + 1);
ddddiag1[d][i - rad] -= b;
ddddiag1[d][i + rad + 1] += b;
// diag2 lines
d = x + y;
i = x - max(0, d - min(h, w) - 3 + 1);
ddddiag2[d][i - rad] -= b;
ddddiag2[d][i + rad + 1] += b;
}
for (int r = 1; r <= h + 2; ++r) {
for (int c = 1; c <= w + 2; ++c) {
ddgrid[r][c] = ddgrid[r - 1][c] + dddvert[r][c];
}
}
for (int r = 1; r < h + 2; ++r) {
for (int c = 1; c <= w + 2; ++c) {
dddiag1grid[r][c] = dddiag1grid[r - 1][c - 1] + ddddiag1[c - r + h + 3 - 1][c - max(0, c - r + h + 3 - 1 - min(h, w) - 3 + 1)];
}
}
for (int r = h + 1; r >= 1; --r) {
for (int c = 1; c <= w + 2; ++c) {
dddiag2grid[r][c] = dddiag2grid[r + 1][c - 1] + ddddiag2[c + r][c - max(0, c + r - min(h, w) - 3 + 1)];
}
}
for (int r = 1; r <= h; ++r) {
for (int c = 1; c <= w; ++c) {
ddgrid[r][c] += dddiag1grid[r][c];
ddgrid[r][c] += dddiag2grid[r][c];
dgrid[r][c] = dgrid[r][c - 1] + ddgrid[r][c];
grid[r][c] = grid[r][c - 1] + dgrid[r][c];
}
}
}
for (int r = 1; r <= h; ++r) {
for (int c = 1; c <= w; ++c) {
ps[r][c] = ps[r - 1][c] + ps[r][c - 1] - ps[r - 1][c - 1] + grid[r][c];
}
}
// for (int r = 1; r <= h; ++r) {
// for (int c = 1; c <= w; ++c) {
// cout << grid[r][c] << " ";
// }
// cout << endl;
// }
int q;
cin >> q;
while (q--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// int s1 = ps[y2][x2] - ps[y2][x1 - 1] - ps[y1 - 1][x2] + ps[y1 - 1][x1 - 1];
// int s2 = 0;
// for (int r = y1; r <= y2; ++r) {
// for (int c = x1; c <= x2; ++c) {
// s2 += grid[r][c];
// }
// }
// if (s1 != s2) {
// cout << s1 << " " << s2 << endl;
// }
long long s = ps[y2][x2] - ps[y2][x1 - 1] - ps[y1 - 1][x2] + ps[y1 - 1][x1 - 1];
int d = (x2 - x1 + 1) * (y2 - y1 + 1);
if (s % d >= (d + 1) / 2) {
cout << s / d + 1 << endl;
} else {
cout << s / d << endl;
}
// cout << ps[y2][x2] - ps[y2][x1 - 1] - ps[y1 - 1][x2] + ps[y1 - 1][x1 - 1] << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
147136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
147204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
39788 KB |
Output is correct |
| 2 |
Correct |
330 ms |
4388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
51288 KB |
Output is correct |
| 2 |
Correct |
332 ms |
4644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
458 ms |
149364 KB |
Output is correct |
| 2 |
Incorrect |
350 ms |
5180 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
413 ms |
61380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
559 ms |
42256 KB |
Output is correct |
| 2 |
Correct |
344 ms |
4856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
527 ms |
37964 KB |
Output is correct |
| 2 |
Correct |
331 ms |
4384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
602 ms |
150016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
592 ms |
149424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
687 ms |
182064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
687 ms |
193436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
236 ms |
380496 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
243 ms |
368820 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
