제출 #886876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886876		awu	Nuclearia (CEOI15_nuclearia)	C++14	15 / 100	687 ms	380496 KiB

nuclearia

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

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