oj.uz

Submission #462337

# Submission time Handle Problem Language Result Execution time Memory
462337 2021-08-10T11:37:48 Z kingfran1907 Nuclearia (CEOI15_nuclearia) C++14
55 / 100
 1000 ms 373184 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;
bool flag = false;
vector< llint > niz[maxn], pr[maxn];
vector< llint > pref[maxn];

int main() {
	scanf("%d%d", &w, &h);
	if (w > h) {
		swap(w, h);
		flag = true;
	}
	
	for (int i = 0; i <= w; i++) 
		for (int j = 0; j <= h + 5; j++) {
			niz[i].push_back(0);
			pr[i].push_back(0);
		}
			
	scanf("%d", &n);
	while (n--) {
		int x, y;
		llint a, b;
		scanf("%d%d%lld%lld", &x, &y, &a, &b); 
		if (flag) swap(x, y);
		
		for (int i = 1; i <= w; i++) {
			llint aa = max(0LL, a - b * abs(i - x));
			llint dist = aa / b;
			
			int ll = max(1, y - abs(i - x));
			int rr = min(h, y + abs(i - x));
			
			int l = max(1LL, ll - dist);
			int r = min((llint)h, rr + dist);
			
			pr[i][l - 1] += aa - b * (ll - l);
			pr[i][l] -= aa - b * (ll - l);
			pr[i][l] += b;
			
			pr[i][ll] -= b;
			pr[i][rr] -= b;
			
			pr[i][r] -= aa - b * (r - rr); 
			pr[i][r] += b;
			pr[i][r + 1] += aa - b * (r - rr);
		}
	}
	for (int i = 0; i <= w; i++) {
		llint tren = pr[i][0];
		for (int j = 1; j <= h; j++) {
			niz[i][j] = tren + niz[i][j - 1]; 
			tren += pr[i][j];
		}
	}
	
	/*
	for (int i = 1; i <= w; i++) {
		for (int j = 1; j <= h; j++) {
			printf("%lld ", niz[i][j]);
		}
		printf("\n");
	}
	*/
	
	for (int i = 0; i <= w; i++) {
		for (int j = 0; j <= h + 5; 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 + 1][j + 1];
			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--;
		if (flag) {
			swap(x1, y1);
			swap(x2, y2);
		}
		
		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:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d", &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~
nuclearia.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%d%d%lld%lld", &x, &y, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   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 303 ms 372004 KB Output is correct
2 Correct 203 ms 215416 KB Output is correct
3 Correct 205 ms 214996 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 372008 KB Output is correct
2 Correct 205 ms 215364 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 276660 KB Output is correct
2 Correct 205 ms 215436 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 274044 KB Output is correct
2 Correct 206 ms 215448 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 371976 KB Output is correct
2 Correct 211 ms 215700 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 263556 KB Output is correct
2 Correct 237 ms 215328 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 280580 KB Output is correct
2 Correct 212 ms 215592 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 250852 KB Output is correct
2 Correct 210 ms 215368 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 373184 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 372948 KB Output is correct

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 255628 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 1091 ms 259360 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 1095 ms 254120 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 1102 ms 255640 KB Time limit exceeded
2 Halted 0 ms 0 KB -