Submission #766442

#	Time	Username	Problem	Language	Result	Execution time	Memory
766442		a_aguilo	Nuclearia (CEOI15_nuclearia)	C++14	0 / 100	1077 ms	280332 KiB

nuclearia

#include<bits/stdc++.h>

using namespace std;

int N, Q, W, H;
vector<vector<long long int>> plants, preSum;

void print(vector<vector<long long int>>& V){
	for(int i = 0; i < W; ++i){
		for(int j = 0; j < H; ++j){
			cout << V[i][j] << " ";
		}
		cout << endl;
	}
}

void calcPreSum(){
	preSum = vector<vector<long long int>>(W, vector<long long int>(H, 0));
	for(int i = 0; i < W; ++i){
		preSum[i][0] = plants[i][0];
		if(i) preSum[i][0] += preSum[i-1][0];
	}
	for(int i = 0; i < H; ++i){
		preSum[0][i] = plants[0][i];
		if(i) preSum[0][i] += preSum[0][i-1];
	}
	for(int i = 1; i < W; ++i){
		for(int j = 1; j < H; ++j){
			preSum[i][j] = plants[i][j] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];
		}
	}
	//print(preSum);
}

long long getSum(int x1, int y1, int x2, int y2){
	long long ans = preSum[x2][y2];
	//cout << ans << endl;
	if(x1 > 0 and y1 > 0){
		ans += preSum[x1 - 1][y1 - 1] - preSum[x1 - 1][y2] - preSum[x2][y1 - 1];
		return ans;
	}else if (x1) ans -= preSum[x1 - 1][y2];
	else if(y1) ans -= preSum[x2][y1 - 1];
	return ans;
}

int main(){
	int x, y, a, b;
	cin >> W >> H;
	plants = vector<vector<long long int>>(W, vector<long long int>(H, 0));
	cin >> N;
	for(int i = 0; i < N; ++i){
		cin >> x >> y >> a >> b;
		x--; y--;
		plants[x][y] += a;
		for(int d = 1; d*b < a; ++d){
			//print();
			//cout << endl;
			//cout << a << " " << d << endl;
			if(y >= d){
				for(int i = max(0, x-d); i < min(W, x+d); ++i){
					plants[i][y-d] += a - b*d;
				}
			}
			if(x+d < W){
				for(int i = max(0, y-d); i < min(H, y+d); ++i)plants[x+d][i] += a - b*d;
			}
			if(y+d < H){
				for(int i = min(W-1, x+d); i > max(-1, x-d); --i)plants[i][y+d] += a - b*d;
			}
			if(x >= d){
				for(int i = min(H-1, y+d); i > max(-1, y-d); --i)plants[x-d][i] += a - b*d;
			}
		}
	}
	//print();
	calcPreSum();
	cin >> Q;
	while(Q--){
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x1--; y1--; x2--; y2--;
		long long sum = getSum(x1, y1, x2, y2);
		//cout << sum << endl;
		long long numSquares = (x2 - x1 + 1)*(y2 - y1 + 1);
		long double q = (long double)sum/(long double)numSquares;
		//if(q*numSquares < sum) q++;
		cout << round(q) << endl;
	}
	return 0;
}

• 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