#pragma GCC optimize("O3") /* pls increase TL this is O(n + q + wh)*/
#pragma GCC target("avx,avx2,sse4")
#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 200000;
vector<vector<uint64_t>> r;
vector<vector<pair<uint64_t, uint64_t>>> rgt, dwn, diag, rgt_corr, dwn_corr;
uint64_t plants[N][4];
void add_plant_source(size_t i, size_t j, uint64_t a, uint64_t b)
{
uint64_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()) /* there ain't no such thing as enough */
{ /* states*/
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<uint64_t, uint64_t> rotate_point(uint64_t i, uint64_t j, uint64_t h)
{
return {h - j - 1, i};
}
void rotate_grid(vector<vector<uint64_t>> &grid, uint64_t h)
{
vector<vector<uint64_t>> res(grid[0].size(), vector<uint64_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<uint64_t>>(w, vector<uint64_t>(h));
for (size_t z = 0; z < 4; ++z)
{
rgt = vector<vector<pair<uint64_t, uint64_t>>>(r.size(), vector<pair<uint64_t, uint64_t>>(r[0].size()));
dwn = vector<vector<pair<uint64_t, uint64_t>>>(r.size(), vector<pair<uint64_t, uint64_t>>(r[0].size()));
diag = vector<vector<pair<uint64_t, uint64_t>>>(r.size(), vector<pair<uint64_t, uint64_t>>(r[0].size()));
rgt_corr = vector<vector<pair<uint64_t, uint64_t>>>(r.size(), vector<pair<uint64_t, uint64_t>>(r[0].size()));
dwn_corr = vector<vector<pair<uint64_t, uint64_t>>>(r.size(), vector<pair<uint64_t, uint64_t>>(r[0].size()));
for (size_t i = 0; i < n; ++i)
{
uint64_t d = plants[i][2] / plants[i][3];
if (!d)
{
if (!(z & 1))
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[0].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;
uint64_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';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1106 ms |
861388 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1097 ms |
861316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
494 ms |
255944 KB |
Output is correct |
| 2 |
Correct |
73 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
581 ms |
284996 KB |
Output is correct |
| 2 |
Correct |
51 ms |
2760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1111 ms |
861376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
917 ms |
352448 KB |
Output is correct |
| 2 |
Correct |
52 ms |
2696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
574 ms |
258460 KB |
Output is correct |
| 2 |
Correct |
53 ms |
3080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
613 ms |
229828 KB |
Output is correct |
| 2 |
Correct |
54 ms |
2632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1121 ms |
867644 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1110 ms |
867708 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
834 ms |
264024 KB |
Output is correct |
| 2 |
Correct |
805 ms |
263796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
825 ms |
263800 KB |
Output is correct |
| 2 |
Correct |
803 ms |
264108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
745 ms |
267864 KB |
Output is correct |
| 2 |
Correct |
709 ms |
265912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
742 ms |
264444 KB |
Output is correct |
| 2 |
Execution timed out |
1118 ms |
867688 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
