oj.uz

Submission #766463

# Submission time Handle Problem Language Result Execution time Memory
766463 2023-06-25T16:46:06 Z a_aguilo Nuclearia (CEOI15_nuclearia) C++14
0 / 100
 1000 ms 276952 KB 
#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;
	long long 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; ((long long) 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 620 ms 274288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 575 ms 274276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 39768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 598 ms 40420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 874 ms 276952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 968 ms 112604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 744 ms 42324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 773 ms 57796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 137300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 137324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 20256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 20192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 20436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 20060 KB Time limit exceeded
2 Halted 0 ms 0 KB -