Submission #369613

#	Time	Username	Problem	Language	Result	Execution time	Memory
369613		ijxjdjd	Nuclearia (CEOI15_nuclearia)	C++14	0 / 100	399 ms	128768 KiB

nuclearia

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = 200000;
int nukes[MAXN][4];
void construct(vector<vector<ll>>& res, int R, int C) {
    res.clear();
    res.resize(R, vector<ll>(C, 0));
}
void add(vector<vector<ll>>& res, int r, int c, ll v) {
    if (r < res.size() && c < res[0].size()) {
        res[r][c] += v;
    }
}
ll get(vector<vector<ll>>& res, int r, int c) {
    if (r < res.size() && c < res[0].size() && r >= 0 && c >= 0) {
        return res[r][c];
    }
    return 0;
}
ll ceil(ll i, ll d) {
    return (i + d-1)/d;
}
void pr(vector<vector<ll>>& res) {
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[0].size(); j++) {
            cerr << res[i][j] << " ";
        }
        cerr << '\n';
    }
}
int main() {
//    freopen("input.in", "r", stdin);
	cin.tie(0);
	cin.sync_with_stdio(0);
	int W, H;
	cin >> W >> H;
	int N;
	cin >> N;
	FR(i, N) {
        cin >> nukes[i][1] >> nukes[i][0] >> nukes[i][2] >> nukes[i][3];
        nukes[i][1]--;
        nukes[i][0]--;
	}
	vector<vector<ll>> diagLeft;
	vector<vector<ll>> diagRight;
	vector<vector<ll>> hori;
	vector<vector<ll>> pref;
	vector<vector<ll>> initial;
	construct(diagLeft, H, W);
	construct(diagRight, H, W);
	construct(hori, H, W);
	construct(pref, H, W);
	construct(initial, H, W);
	FR(i, N) {
        int s = (nukes[i][2] - 1)/nukes[i][3];
        int st = nukes[i][2] - s*nukes[i][3];
        add(diagLeft, nukes[i][0]-s, nukes[i][1]-s, -nukes[i][3]);
        add(diagLeft, nukes[i][0]+s+1, nukes[i][1]+s+1, nukes[i][3]);
        add(diagRight, nukes[i][0]-s, nukes[i][1]+s, -nukes[i][3]);
        add(diagRight, nukes[i][0]+s+1, nukes[i][1]-s-1, nukes[i][3]);
        add(hori, nukes[i][0]-s, nukes[i][1]-s, nukes[i][3]);
        add(hori, nukes[i][0]-s, nukes[i][1]+s+1, -nukes[i][3]);
        add(hori, nukes[i][0]+s, nukes[i][1]-s, nukes[i][3]);
        add(hori, nukes[i][0] + s, nukes[i][1]+s+1, -nukes[i][3]);
        add(initial, nukes[i][0]-s, nukes[i][1]-s, st);
        add(initial, nukes[i][0]+s+1, nukes[i][1]-s, -st);
        add(initial, nukes[i][0]-s, nukes[i][1]+s+1,-st);
        add(initial, nukes[i][0]+s+1, nukes[i][1]+s+1, st);
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            hori[i][j] += get(hori, i, j-1);
            diagLeft[i][j] += get(diagLeft, i-1, j-1);
            diagRight[i][j] += get(diagRight, i-1, j+1);
            initial[i][j] +=  - get(initial, i-1, j-1) + get(initial, i-1, j) + get(initial, i, j-1);
            pref[i][j] = hori[i][j] + diagLeft[i][j] + diagRight[i][j] + get(pref, i-1, j);
        }
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            pref[i][j] += get(pref, i-1, j);
            initial[i][j] += get(pref, i-1, j);
        }
    }
//    pr(initial);
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            initial[i][j] +=  - get(initial, i-1, j-1) + get(initial, i-1, j) + get(initial, i, j-1);
        }
    }
    int Q;
    cin >> Q;
    FR(i, Q) {
        int r1, r2, c1, c2;
        cin >> c1 >> r1 >> c2 >> r2;
        c1--, r1--, c2--, r2--;
        cout << ceil(get(initial, r2, c2) - get(initial, r1-1, c2) - get(initial, r2, c1-1) + get(initial, r1-1, c1-1), (r2-r1+1)*(c2-c1+1)) << '\n';
    }
	return 0;
}

Compilation message (stderr)

nuclearia.cpp: In function 'void add(std::vector<std::vector<long long int> >&, int, int, ll)':
nuclearia.cpp:16:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     if (r < res.size() && c < res[0].size()) {
      |         ~~^~~~~~~~~~~~
nuclearia.cpp:16:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     if (r < res.size() && c < res[0].size()) {
      |                           ~~^~~~~~~~~~~~~~~
nuclearia.cpp: In function 'll get(std::vector<std::vector<long long int> >&, int, int)':
nuclearia.cpp:21:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (r < res.size() && c < res[0].size() && r >= 0 && c >= 0) {
      |         ~~^~~~~~~~~~~~
nuclearia.cpp:21:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (r < res.size() && c < res[0].size() && r >= 0 && c >= 0) {
      |                           ~~^~~~~~~~~~~~~~~
nuclearia.cpp: In function 'void pr(std::vector<std::vector<long long int> >&)':
nuclearia.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < res.size(); i++) {
      |                     ~~^~~~~~~~~~~~
nuclearia.cpp:31:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int j = 0; j < res[0].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 2
• Subtask 3: 0 / 3
• Subtask 4: 0 / 2
• Subtask 5: 0 / 6
• Subtask 6: 0 / 4
• Subtask 7: 0 / 6
• Subtask 8: 0 / 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