oj.uz

답안 #37716

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37716 2017-12-27T08:32:23 Z aome Nuclearia (CEOI15_nuclearia) C++14
0 / 100
 289 ms 138896 KB 
#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, 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;
    if (x > y) {
        // update col 1
        cntL = min(cnt, x - 1);
        col[x] -= val;
        x -= cntL, cnt -= cntL;
        col[x] += val;
    }
    else {
        // 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, 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
    if (x < y) {
        int cntL = min(cnt, h - y);
        // update row 1
        if (y < h) row[y + 1] += val;
        y += cntL, cnt -= cntL;
        if (y < h) row[y + 1] -= val;
    }
}

void update2(int x, int y, int val, int cnt) {
    // diagonal
    int cntD = min(cnt, 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
    if (x > y) {
        int cntL = min(cnt, w - x);
        // update col 1
        if (x < w) col[x + 1] += val;
        x += cntL, cnt -= cntL;
        if (x < w) col[x + 1] -= val;
    }
}

void update3(int x, int y, int val, int cnt) {
    // diagonal
    int cntD = min(cnt, 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)];
        }
	}
	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) 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)];
		}
	}
}

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() {
	ios::sync_with_stdio(false);
	cin >> w >> h >> n;

	// update offline plants

	for (int i = 1; i <= n; ++i) {
		int x, y, a, b;
		cin >> 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;
	cin >> q;
	while (q--) {
        int x0, y0, x1, y1;
        cin >> x0 >> y0 >> x1 >> y1;
        int sz = (x1 - x0 + 1) * (y1 - y0 + 1);
        long long res = calcRes(x0, y0, x1, y1);
        printf("%lld\n", (res + sz / 2) / sz);
	}

}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 216 ms 138896 KB Execution killed because of forbidden syscall writev (20)

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 203 ms 138896 KB Execution killed because of forbidden syscall writev (20)

Subtask #11
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 256 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 223 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #13
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 196 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 289 ms 138896 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -