Submission #462273

#	Time	Username	Problem	Language	Result	Execution time	Memory
462273		kingfran1907	Nuclearia (CEOI15_nuclearia)	C++14	30 / 100	1099 ms	303548 KiB

nuclearia

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 3e6+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, q;
int w, h;
vector< llint > niz[maxn];
vector< llint > pref[maxn];

int main() {
	scanf("%d%d", &w, &h);
	for (int i = 0; i < w; i++) 
		for (int j = 0; j < h; j++)
			niz[i].push_back(0);
			
	scanf("%d", &n);
	while (n--) {
		int x, y;
		llint a, b;
		scanf("%d%d%lld%lld", &x, &y, &a, &b); x--, y--;
		
		for (int i = 0; i < w; i++) {
			for (int j = 0; j < h; j++) {
				int dis = max(abs(i - x), abs(j - y));
				llint kol = max(0LL, a - b * dis);
				niz[i][j] += kol;
			}
		}
	}
	
	for (int i = 0; i <= w; i++) {
		for (int j = 0; j <= h; j++) {
			pref[i].push_back(0);
		}
	}
	
	for (int i = 0; i < w; i++) {
		for (int j = 0; j < h; j++) {
			pref[i + 1][j + 1] = niz[i][j];
			pref[i + 1][j + 1] += pref[i + 1][j];
		}
	}
	for (int i = 0; i < w; i++) {
		for (int j = 0; j < h; j++) {
			pref[i + 1][j + 1] += pref[i][j + 1];
		}
	}
	
	scanf("%d", &q);
	while (q--) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2); x1--, y1--;
		
		llint sum = pref[x2][y2] - pref[x1][y2] - pref[x2][y1] + pref[x1][y1];
		llint cnt = (llint)(x2 - x1) * (y2 - y1);
		
		llint sol = sum / cnt;
		llint rem = sum % cnt;
		
		if (rem * 2 >= cnt) printf("%lld\n", sol + 1);
		else printf("%lld\n", sol);
	}
	return 0;
}

Compilation message (stderr)

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%d%d", &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~
nuclearia.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d%d%lld%lld", &x, &y, &a, &b); x--, y--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%d%d%d%d", &x1, &y1, &x2, &y2); 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: 0 / 15
• Subtask 10: 0 / 10
• Subtask 11: 0 / 15
• Subtask 12: 0 / 10
• Subtask 13: 0 / 12
• Subtask 14: 0 / 8