#pragma GCC optimize("O3")
#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())
{
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 |
1097 ms |
861312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
861600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
509 ms |
255924 KB |
Output is correct |
| 2 |
Correct |
53 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
591 ms |
285104 KB |
Output is correct |
| 2 |
Correct |
53 ms |
2648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1102 ms |
861320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
913 ms |
352536 KB |
Output is correct |
| 2 |
Correct |
51 ms |
2696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
571 ms |
258400 KB |
Output is correct |
| 2 |
Correct |
53 ms |
3020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
622 ms |
229684 KB |
Output is correct |
| 2 |
Correct |
55 ms |
2744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1124 ms |
867672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1101 ms |
867648 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
835 ms |
263980 KB |
Output is correct |
| 2 |
Correct |
838 ms |
263664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
820 ms |
263840 KB |
Output is correct |
| 2 |
Correct |
801 ms |
271552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
751 ms |
267816 KB |
Output is correct |
| 2 |
Correct |
731 ms |
265880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
760 ms |
264412 KB |
Output is correct |
| 2 |
Execution timed out |
1120 ms |
871436 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
