Submission #749374

#	Time	Username	Problem	Language	Result	Execution time	Memory
749374		finn__	Nuclearia (CEOI15_nuclearia)	C++17	56 / 100	1124 ms	871436 KiB

nuclearia

#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';
    }
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 2
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 0 / 6
• Subtask 6: 4 / 4
• Subtask 7: 6 / 6
• Subtask 8: 4 / 4
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10
• Subtask 11: 15 / 15
• Subtask 12: 10 / 10
• Subtask 13: 12 / 12
• Subtask 14: 0 / 8