oj.uz

Submission #462294

# Submission time Handle Problem Language Result Execution time Memory
462294 2021-08-10T10:17:35 Z kingfran1907 Nuclearia (CEOI15_nuclearia) C++14
39 / 100
 1000 ms 189996 KB 
#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];
llint ac[maxn];
llint pr[maxn];

int main() {
	scanf("%d%d", &w, &h);
	if (h == 1) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			int x, y;
			llint a, b;
			scanf("%d%d%lld%lld", &x, &y, &a, &b);
			
			llint dis = a / b;
			int l = max(1LL, x - dis);
			int r = min((llint)w, x + dis);
			
			pr[l - 1] += a - b * (x - l);
			pr[l] -= a - b * (x - l);
			pr[l] += b;
			
			pr[x] -= b + b;
			
			pr[r] -= a - b * (r - x); 
			pr[r] += b;
			pr[r + 1] -= a - b * (r - x);
		}
		
		llint tren = pr[0];
		for (int i = 1; i <= w; i++) {
			ac[i] = ac[i - 1] + tren;
			tren += pr[i];
		}
		
		for (int i = 1; i <= w; i++) ac[i] += ac[i - 1];
		
		scanf("%d", &q);
		while (q--) {
			int x1, y1, x2, y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			
			llint sum = ac[x2] - ac[x1 - 1];
			llint cnt = x2 - x1 + 1;
			
			llint sol = sum / cnt;
			llint rem = sum % cnt;
			
			if (rem * 2 >= cnt) printf("%lld\n", sol + 1);
			else printf("%lld\n", sol);
		}
		return 0;
	}
	
	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

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d%d", &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~
nuclearia.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
nuclearia.cpp:30:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |    scanf("%d%d%lld%lld", &x, &y, &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
nuclearia.cpp:58:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d%d%lld%lld", &x, &y, &a, &b); x--, y--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%d%d%d%d", &x1, &y1, &x2, &y2); x1--, y1--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 161092 KB Output is correct
2 Correct 170 ms 143536 KB Output is correct
3 Correct 178 ms 143164 KB Output is correct

Subtask #2
0 / 2.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 181392 KB Output is correct
2 Correct 160 ms 143620 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 182024 KB Output is correct
2 Correct 172 ms 143576 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 162948 KB Output is correct
2 Correct 175 ms 143704 KB Output is correct

Subtask #6
0 / 4.0

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

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 186856 KB Output is correct
2 Correct 176 ms 143736 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 182784 KB Output is correct
2 Correct 164 ms 143556 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 189996 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 345 ms 189996 KB Output isn't correct

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 161268 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 1087 ms 161220 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 1094 ms 161472 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 1099 ms 161220 KB Time limit exceeded
2 Halted 0 ms 0 KB -