#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse4")
#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 200000;
vector<vector<int64_t>> r;
vector<vector<pair<int64_t, int64_t>>> rgt, dwn, diag, rgt_corr, dwn_corr;
int64_t plants[N][4];
void add_plant_source(size_t i, size_t j, int64_t a, int64_t b)
{
int64_t d = a / b;
r[i][j] += a;
if (!d)
return;
rgt[i][j].first += a;
rgt[i][j].second -= b;
dwn[i][j].first += a;
dwn[i][j].second -= b;
diag[i][j].first += a;
diag[i][j].second -= b;
if (i + d + 1 < r.size())
{
r[i + d + 1][j] += (d + 1) * b - a;
rgt[i + d + 1][j].first += (d + 1) * b - a;
rgt[i + d + 1][j].second += b;
rgt_corr[i + d + 1][j].first += (d + 1) * b - a;
rgt_corr[i + d + 1][j].second += b;
}
if (j + d + 1 < r[i].size())
{
r[i][j + d + 1] += (d + 1) * b - a;
dwn[i][j + d + 1].first += (d + 1) * b - a;
dwn[i][j + d + 1].second += b;
dwn_corr[i][j + d + 1].first += (d + 1) * b - a;
dwn_corr[i][j + d + 1].second += b;
}
if (i + d + 1 < r.size() && j + d + 1 < r[i].size())
{
r[i + d + 1][j + d + 1] += (d + 1) * b - a;
rgt_corr[i + d + 1][j + d + 1].first -= (d + 1) * b - a;
rgt_corr[i + d + 1][j + d + 1].second -= b;
dwn_corr[i + d + 1][j + d + 1].first -= (d + 1) * b - a;
dwn_corr[i + d + 1][j + d + 1].second -= b;
diag[i + d + 1][j + d + 1].first += (d + 1) * b - a;
diag[i + d + 1][j + d + 1].second += b;
}
}
void propagate_values()
{
for (size_t i = 0; i < r.size(); ++i)
for (size_t j = 0; j < r[i].size(); ++j)
{
if (i + 1 < r.size())
{
r[i + 1][j] += rgt[i][j].first + rgt[i][j].second;
rgt[i + 1][j].first += rgt[i][j].first + rgt[i][j].second;
rgt[i + 1][j].second += rgt[i][j].second;
dwn[i + 1][j].first += dwn_corr[i][j].first;
dwn[i + 1][j].second += dwn_corr[i][j].second;
dwn_corr[i + 1][j].first += dwn_corr[i][j].first;
dwn_corr[i + 1][j].second += dwn_corr[i][j].second;
r[i + 1][j] += dwn_corr[i][j].first;
}
if (j + 1 < r[i].size())
{
r[i][j + 1] += dwn[i][j].first + dwn[i][j].second;
dwn[i][j + 1].first += dwn[i][j].first + dwn[i][j].second;
dwn[i][j + 1].second += dwn[i][j].second;
rgt[i][j + 1].first += rgt_corr[i][j].first;
rgt[i][j + 1].second += rgt_corr[i][j].second;
rgt_corr[i][j + 1].first += rgt_corr[i][j].first;
rgt_corr[i][j + 1].second += rgt_corr[i][j].second;
r[i][j + 1] += rgt_corr[i][j].first;
}
if (i + 1 < r.size() && j + 1 < r[i].size())
{
r[i + 1][j + 1] += diag[i][j].first + diag[i][j].second;
rgt[i + 1][j + 1].first += diag[i][j].first + diag[i][j].second;
rgt[i + 1][j + 1].second += diag[i][j].second;
dwn[i + 1][j + 1].first += diag[i][j].first + diag[i][j].second;
dwn[i + 1][j + 1].second += diag[i][j].second;
diag[i + 1][j + 1].first += diag[i][j].first + diag[i][j].second;
diag[i + 1][j + 1].second += diag[i][j].second;
}
}
}
inline pair<int64_t, int64_t> rotate_point(int64_t i, int64_t j, int64_t h)
{
return {h - j - 1, i};
}
void rotate_grid(vector<vector<int64_t>> &grid, int64_t h)
{
vector<vector<int64_t>> res(grid[0].size(), vector<int64_t>(grid.size()));
for (size_t i = 0; i < grid.size(); ++i)
for (size_t j = 0; j < grid[i].size(); ++j)
{
auto const [i_, j_] = rotate_point(i, j, h);
res[i_][j_] = grid[i][j];
}
swap(grid, res);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t w, h, n;
cin >> w >> h >> n;
for (size_t i = 0; i < n; ++i)
{
cin >> plants[i][0] >> plants[i][1] >> plants[i][2] >> plants[i][3];
--plants[i][0];
--plants[i][1];
}
r = vector<vector<int64_t>>(w, vector<int64_t>(h));
for (size_t z = 0; z < 4; ++z)
{
rgt = vector<vector<pair<int64_t, int64_t>>>(r.size(), vector<pair<int64_t, int64_t>>(r[0].size()));
dwn = vector<vector<pair<int64_t, int64_t>>>(r.size(), vector<pair<int64_t, int64_t>>(r[0].size()));
diag = vector<vector<pair<int64_t, int64_t>>>(r.size(), vector<pair<int64_t, int64_t>>(r[0].size()));
rgt_corr = vector<vector<pair<int64_t, int64_t>>>(r.size(), vector<pair<int64_t, int64_t>>(r[0].size()));
dwn_corr = vector<vector<pair<int64_t, int64_t>>>(r.size(), vector<pair<int64_t, int64_t>>(r[0].size()));
for (size_t i = 0; i < n; ++i)
{
int64_t d = plants[i][2] / plants[i][3];
if (!d)
{
r[plants[i][0]][plants[i][1]] += plants[i][2];
}
else
{
if (!(z & 1))
add_plant_source(plants[i][0], plants[i][1], plants[i][2], plants[i][3]);
else if (plants[i][0] + 1 < r.size() && plants[i][1] + 1 < r[i].size())
add_plant_source(plants[i][0] + 1, plants[i][1] + 1, plants[i][2] - plants[i][3], plants[i][3]);
}
}
propagate_values();
rotate_grid(r, h);
for (size_t i = 0; i < n; ++i)
tie(plants[i][0], plants[i][1]) = rotate_point(plants[i][0], plants[i][1], h);
swap(w, h);
}
for (size_t i = 0; i < n; ++i)
r[plants[i][0]][plants[i][1]] -= plants[i][2];
for (size_t i = 0; i < r.size(); ++i)
for (size_t j = 1; j < r[i].size(); ++j)
r[i][j] += r[i][j - 1];
for (size_t j = 0; j < r[0].size(); ++j)
for (size_t i = 1; i < r.size(); ++i)
r[i][j] += r[i - 1][j];
size_t q;
cin >> q;
while (q--)
{
size_t i1, i2, j1, j2;
cin >> i1 >> i2 >> j1 >> j2, --i1, --j1, --i2, --j2;
int64_t sum = r[j1][j2] - (i1 ? r[i1 - 1][j2] : 0) - (i2 ? r[j1][i2 - 1] : 0) + (i1 && i2 ? r[i1 - 1][i2 - 1] : 0);
cout << (sum + ((j1 - i1 + 1) * (j2 - i2 + 1)) / 2) / ((j1 - i1 + 1) * (j2 - i2 + 1)) << '\n';
}
}
Compilation message
nuclearia.cpp: In function 'int main()':
nuclearia.cpp:143:43: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | else if (plants[i][0] + 1 < r.size() && plants[i][1] + 1 < r[i].size())
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~
nuclearia.cpp:143:74: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | else if (plants[i][0] + 1 < r.size() && plants[i][1] + 1 < r[i].size())
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1105 ms |
861408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1106 ms |
861380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
602 ms |
256024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
582 ms |
285008 KB |
Output is correct |
| 2 |
Incorrect |
55 ms |
2648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1102 ms |
861348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
936 ms |
352792 KB |
Output is correct |
| 2 |
Correct |
58 ms |
2768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
579 ms |
258284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
631 ms |
229760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1098 ms |
867556 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1111 ms |
867688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
828 ms |
264140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
833 ms |
263864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
505 ms |
538108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
637 ms |
531336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
