Submission #1111168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111168		Ghulam_Junaid	Nuclearia (CEOI15_nuclearia)	C++17	55 / 100	1081 ms	436792 KiB

nuclearia

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const ll N = 2.5e6 + 100;
vector<ll> atl[N], atr[N], inc[N];
 
int main(){
	ll n, w, h;
	scanf("%lld%lld", &w, &h);
	scanf("%lld", &n);
 
 
	if (h == 1){
	ll mat[h+5][w+5] = {0}, dif[h+5][w+5] = {0};
 
	for (ll i=1; i<=n; i++){
		ll x, y, a, b;
		scanf("%lld%lld%lld%lld", &y, &x, &a, &b);
		
		ll imp = a / b;
		ll l = max(1ll, y - imp);
		ll r = min(w, y + imp);
 
		// cout << l << " " << r << endl;
 
		dif[x][l] += a;
		dif[x][r + 1] -= a;
 
		atl[y].push_back(b);
		atr[r].push_back(b);
		inc[l].push_back(b);
 
		dif[x][y] += b * y;
		dif[x][r + 1] -= b * y;
 
		dif[x][l] += b * (w - y + 1);
		dif[x][y + 1] -= b * (w - y + 1);
 
		// for (ll p = 1; p <= h; p++){
		// 	for (ll q = 1; q <= w; q++){
		// 		ll d = max(abs(p - x), abs(q - y));
		// 		mat[p][q] += max(0ll , a - b * d);
		// 	}
		// }
	}
 
	ll sm = 0;
	for (ll i=1; i<=w; i++){
		for (ll x : atl[i])
			sm -= x;
		mat[1][i] += sm * i;
		for (ll x : atr[i])
			sm += x;
	}
 
	sm = 0;
	for (ll i=w; i>0; i--){
		for (ll b : atl[i])
			sm -= b;
		mat[1][i] += sm * (w - i + 1);
		for (ll b : inc[i])
			sm += b;
	}
 
	for (ll i=1; i<=w; i++){
		dif[1][i] += dif[1][i-1];
		mat[1][i] += dif[1][i];
	}
 
	// for (int i=1; i<=w; i++)
	// 	cout << mat[1][i] << " ";
	// cout << endl << endl;
 
	for (ll i = 1; i <= h; i++)
		for (ll j = 1; j <= w; j++)
			mat[i][j] += mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1];
 
	ll q;
	scanf("%lld", &q);
 
	for (ll i = 0; i < q; i++){
		ll lx, ly, rx, ry;
		scanf("%lld%lld%lld%lld", &ly, &lx, &ry, &rx);
 
		ll sm = mat[rx][ry];
		sm -= mat[lx - 1][ry];
		sm -= mat[rx][ly - 1];
		sm += mat[lx - 1][ly - 1];
 
		ll cells = (rx - lx + 1) * (ry - ly + 1);
 
		ll avg = sm / cells;
		ll r = sm % cells;
		avg += (r >= (cells / 2 + cells % 2));
 
		printf("%lld\n", avg);
	}
 
	return 0;}
 
	ll mat[h+1][w+1] = {0};
 
	for (ll i=1; i<=n; i++){
		ll x, y, a, b;
		scanf("%lld%lld%lld%lld", &y, &x, &a, &b);
		
		for (ll p = 1; p <= h; p++){
			for (ll q = 1; q <= w; q++){
				ll d = max(abs(p - x), abs(q - y));
				mat[p][q] += max(0ll , a - b * d);
			}
		}
	}
 
	for (ll i = 1; i <= h; i++)
		for (ll j = 1; j <= w; j++)
			mat[i][j] += mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1];
 
	ll q;
	scanf("%lld", &q);
 
	for (ll i = 0; i < q; i++){
		ll lx, ly, rx, ry;
		scanf("%lld%lld%lld%lld", &ly, &lx, &ry, &rx);
 
		ll sm = mat[rx][ry];
		sm -= mat[lx - 1][ry];
		sm -= mat[rx][ly - 1];
		sm += mat[lx - 1][ly - 1];
 
		ll cells = (rx - lx + 1) * (ry - ly + 1);
 
		ll avg = sm / cells;
		ll r = sm % cells;
		avg += (r >= (cells / 2 + cells % 2));
 
		printf("%lld\n", avg);
	}
}

Compilation message (stderr)

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%lld%lld", &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
nuclearia.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%lld%lld%lld%lld", &y, &x, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%lld", &q);
      |  ~~~~~^~~~~~~~~~~~
nuclearia.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%lld%lld%lld%lld", &ly, &lx, &ry, &rx);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   scanf("%lld%lld%lld%lld", &y, &x, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |  scanf("%lld", &q);
      |  ~~~~~^~~~~~~~~~~~
nuclearia.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |   scanf("%lld%lld%lld%lld", &ly, &lx, &ry, &rx);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 0 / 15
• Subtask 12: 0 / 10
• Subtask 13: 0 / 12
• Subtask 14: 0 / 8