Submission #37725

#	Time	Username	Problem	Language	Result	Execution time	Memory
37725		aome	Nuclearia (CEOI15_nuclearia)	C++14	90 / 100	579 ms	138736 KiB

nuclearia

#include <bits/stdc++.h>
using namespace std;

const int N = 2500005;

int w, h, n, q;
long long a[4][N];
long long row[N], col[N];
long long sum[N];

int encode(int x, int y) {
	return (x - 1) * h + y;
}

void updateRes(int x0, int y0, int x1, int y1, int val) {
	sum[encode(x0, y0)] += val;
	if (y1 < h) sum[encode(x0, y1 + 1)] -= val;
	if (x1 < w) sum[encode(x1 + 1, y0)] -= val;
	if (y1 < h && x1 < w) sum[encode(x1 + 1, y1 + 1)] += val;
}

void update0(int x, int y, int val, int cnt) {
    // diagonal
	int cntD = min(cnt - 1, min(x - 1, y - 1));
    if (x < w && y < h) a[0][encode(x + 1, y + 1)] -= val;
    cnt -= cntD + 1, x -= cntD, y -= cntD;
    a[0][encode(x, y)] += val;
    // line
    int cntL;
    // update col 1
    cntL = min(cnt, x - 1);
    col[x] -= val;
    x -= cntL, cnt -= cntL;
    col[x] += val;
    // update row 1
    cntL = min(cnt, y - 1);
    row[y] -= val;
    y -= cntL, cnt -= cntL;
    row[y] += val;
    if (cnt) sum[1] += val * cnt;
}

void update1(int x, int y, int val, int cnt) {
    // diagonal
    int cntD = min(cnt - 1, min(x - 1, h - y));
    if (x < w && y > 1) a[1][encode(x + 1, y - 1)] -= val;
    cnt -= cntD + 1, x -= cntD, y += cntD;
    a[1][encode(x, y)] += val;
    // line
    int cntL = min(cnt, h - y);
    // update row 1
    if (y < h) row[y + 1] += val;
    y += cntL;
    if (y < h) row[y + 1] -= val;
}

void update2(int x, int y, int val, int cnt) {
    // diagonal
    int cntD = min(cnt - 1, min(w - x, y - 1));
    if (x > 1 && y < h) a[2][encode(x - 1, y + 1)] -= val;
    cnt -= cntD + 1, x += cntD, y -= cntD;
    a[2][encode(x, y)] += val;
    // line
    int cntL = min(cnt, w - x);
    // update col 1
    if (x < w) col[x + 1] += val;
    x += cntL;
    if (x < w) col[x + 1] -= val;
}

void update3(int x, int y, int val, int cnt) {
    // diagonal
    int cntD = min(cnt - 1, min(w - x, h - y));
    if (x > 1 && y > 1) a[3][encode(x - 1, y - 1)] -= val;
    x += cntD, y += cntD;
    a[3][encode(x, y)] += val;
}

void updateAll() {
	// row 1
    for (int i = 2; i <= h; ++i) row[i] += row[i - 1];
	// col 1
	for (int i = 2; i <= w; ++i) col[i] += col[i - 1];

	// diagonal -1, -1
	for (int i = 2; i <= w; ++i) {
        for (int j = 2; j <= h; ++j) {
            a[0][encode(i, j)] += a[0][encode(i - 1, j - 1)];
        }
	}
	// diagonal -1, +1
	for (int i = 2; i <= w; ++i) {
        for (int j = h - 1; j >= 1; --j) {
            a[1][encode(i, j)] += a[1][encode(i - 1, j + 1)];
        }
	}
	// diagonal +1, -1
	for (int i = w - 1; i >= 1; --i) {
        for (int j = 2; j <= h; ++j) {
            a[2][encode(i, j)] += a[2][encode(i + 1, j - 1)];
        }
	}
	// diagonal +1, +1
	for (int i = w - 1; i >= 1; --i) {
        for (int j = h - 1; j >= 1; --j) {
            a[3][encode(i, j)] += a[3][encode(i + 1, j + 1)];
        }
	}
}

void debugDiagonal(int type) {
    cout << "Diagonal " << type << '\n';
    for (int i = 1; i <= w; ++i) {
        for (int j = 1; j <= h; ++j) {
            cout << a[type][encode(i, j)] << ' ';
        }
        cout << '\n';
    }
}

void debugRow() {
    cout << "Row\n";
    for (int i = 1; i <= h; ++i) cout << row[i] << ' '; cout << '\n';
}

void debugCol() {
    cout << "Col\n";
    for (int i = 1; i <= w; ++i) cout << row[i] << ' '; cout << '\n';
}

void calcIndividual() {
    // sum -> value of cell (i, j)

    // for col
	for (int i = 1; i <= w; ++i) sum[encode(i, 1)] += col[i];
	// for row
	for (int i = 1; i <= h; ++i) sum[encode(1, i)] += row[i];

	for (int i = 1; i <= w; ++i) {
		for (int j = 1; j <= h; ++j) {
            // for diagonal
            for (int k = 0; k <= 3; ++k) {
                sum[encode(i, j)] += a[k][encode(i, j)];
            }
			if (i > 1) sum[encode(i, j)] += sum[encode(i - 1, j)];
			if (j > 1) sum[encode(i, j)] += sum[encode(i, j - 1)];
			if (i > 1 && j > 1) sum[encode(i, j)] -= sum[encode(i - 1, j - 1)];
//			cout << sum[encode(i, j)] << ' ';
		}
//		cout << '\n';
	}
}

void calcSum() {
    // sum -> sum values of cells from (1, 1) -> (i, j)

	for (int i = 1; i <= w; ++i) {
		for (int j = 1; j <= h; ++j) {
		    if (i > 1 && j > 1) sum[encode(i, j)] -= sum[encode(i - 1, j - 1)];
			if (i > 1) sum[encode(i, j)] += sum[encode(i - 1, j)];
			if (j > 1) sum[encode(i, j)] += sum[encode(i, j - 1)];
		}
	}
}

long long calcRes(int x0, int y0, int x1, int y1) {
    long long res = sum[encode(x1, y1)];
    if (x0 > 1) res -= sum[encode(x0 - 1, y1)];
    if (y0 > 1) res -= sum[encode(x1, y0 - 1)];
    if (x0 > 1 && y0 > 1) res += sum[encode(x0 - 1, y0 - 1)];
    return res;
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
	scanf("%d %d %d", &w, &h, &n);

	// update offline plants

	for (int i = 1; i <= n; ++i) {
		int x, y, a, b;
		scanf("%d %d %d %d", &x, &y, &a, &b);
		int tmp = min(a / b, max(max(x - 1, w - x), max(y - 1, h - y)));
		// update all covered cells
		updateRes(max(x - tmp, 1), max(y - tmp, 1), min(x + tmp, w), min(y + tmp, h), a - b * tmp);

		// update diagonal -1, -1
		update0(x, y, b, tmp);
		// update diagonal -1, +1
		if (y < h) update1(x, y + 1, -b, tmp);
		// update diagonal +1, -1
		if (x < w) update2(x + 1, y, -b, tmp);
		// update diagonal +1, +1
		if (x < w && y < h) update3(x + 1, y + 1, b, tmp);
	}

	// prepare for answering queries

    updateAll();
//    for (int i = 0; i < 4; ++i) debugDiagonal(i);
//    debugRow(), debugCol();

    calcIndividual();

    calcSum();

	// queries
	int q;
	scanf("%d", &q);
	while (q--) {
        int x0, y0, x1, y1;
        scanf("%d %d %d %d", &x0, &y0, &x1, &y1);
        int sz = (x1 - x0 + 1) * (y1 - y0 + 1);
        long long res = calcRes(x0, y0, x1, y1);
        printf("%llu\n", (res + sz / 2) / sz);
	}

}

Compilation message (stderr)

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:177:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &w, &h, &n);
                               ^
nuclearia.cpp:183:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &x, &y, &a, &b);
                                       ^
nuclearia.cpp:210:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
nuclearia.cpp:213:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &x0, &y0, &x1, &y1);
                                                 ^

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