oj.uz

Submission #39723

# Submission time Handle Problem Language Result Execution time Memory
39723 2018-01-18T02:04:43 Z farmersrice Nuclearia (CEOI15_nuclearia) C++14
40 / 100
 1000 ms 299848 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#pragma GCC target ("avx,tune=native")
//Use above if bruteforcing with lots of small operations. Or just use it anytime, there's no downside. AVX is better slightly
/*
TASK: hidden
LANG: C++11
*/
using namespace std;
typedef long long ll;
typedef pair<int, int> pair2;
typedef pair<int, pair<int, int> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 200013
#define MAXA 2500013
#define INF 1000000000000000000LL
#define mp make_pair
#define add push_back
#define remove pop

int n;
int w, h, q;
int x[MAXN], y[MAXN];
ll a[MAXN], b[MAXN];
bool swapped;

ll * trees[4][MAXA];
ll * metadelta[MAXA]; //ADDS OVER EACH CELL AFTER AND INCLUDING ITSELF
 
void update(int i, int j, ll sign) {
	if (i < 0 || j < 0) return;
	//cout << "Updating " << i << ' ' << j << ' ' << sign << endl;
	trees[0][i + 1][j + 1] += sign;
	trees[1][i + 1][j + 1] += sign * (i + 1);
	trees[2][i + 1][j + 1] += sign * (j + 1);
	trees[3][i + 1][j + 1] += sign * (i + 1) * (j + 1);
	/*
	trees[0].update(i, j, sign);
	trees[1].update(i, j, sign * (i + 1));
	trees[2].update(i, j, sign * (j + 1));
	trees[3].update(i, j, sign * (i + 1) * (j + 1));*/
	//cout << "Trees 3 update " << i << ' ' << j << " with " << sign * (i + 1) * (j + 1) << endl;
}

void makeArray(int a) {
	for (int i = 1; i <= w; i++) {
		for (int j = 1; j <= h; j++) {
			trees[a][i][j] += trees[a][i - 1][j] + trees[a][i][j - 1] - trees[a][i - 1][j - 1];
			//cout << "array made " << i << ' ' << j << " value " << trees[a][i][j] << endl;
		}
	}
}

ll getSum(int i, int j) {
	if (i < 0 || j < 0) return 0;
	ll answer = 0;
	answer += trees[3][i + 1][j + 1];
	//cout << "Trees 3 query " << i << ' ' << j << " is " << answer << endl;
	answer += (i + 1) * (trees[2][w][j + 1] - trees[2][i + 1][j + 1]);
	answer += (j + 1) * (trees[1][i + 1][h] - trees[1][i + 1][j + 1]);
	answer += (i + 1) * (j + 1) * (trees[0][w][h] - trees[0][w][j + 1] - trees[0][i + 1][h] + trees[0][i + 1][j + 1]);
	return answer;
}
 
ll getSum(int a, int b, int c, int d) {
	//a, b is bottom left
	//c, d is top right
 
	return getSum(c, d) - getSum(a - 1, d) - getSum(c, b - 1) + getSum(a - 1, b - 1);
}
 
void updateRect(int a, int b, int c, int d, ll value) {
	update(c, d, value); update(a - 1, d, -value); update(c, b - 1, -value); update(a - 1, b - 1, value);
}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	scanf("%d%d", &w, &h);
	scanf("%d", &n);
	//cin >> w >> h;
	//assert(h == 1);
	//cin >> n;

	for (int i = 0; i < n; i++) {
		//cin >> x[i] >> y[i] >> a[i] >> b[i];
		scanf("%d%d%lld%lld", &x[i], &y[i], &a[i], &b[i]);
		x[i]--;
		y[i]--;
	}

	if (w > h) {
		swap(w, h);

		for (int i = 0; i < n; i++) {
			swap(x[i], y[i]);
		}

		swapped = true;
	}

	
	for (int a = 0; a < 4; a++) for (int i = 0; i <= w; i++) {
		trees[a][i] = new ll[h + 1];

		for (int j = 0; j < h + 1; j++) {
			trees[a][i][j] = 0;
		}
	}

	for (int i = 0; i <= w; i++) {
		metadelta[i] = new ll[h + 1];

		for (int j = 0; j < h + 1; j++) {
			metadelta[i][j] = 0;
		}
	}

	for (int i = 0; i < n; i++) {
		ll possible = (a[i] - 1) / b[i];

		if (possible == 0) {
			metadelta[x[i]][y[i]] += a[i];
			if (y[i] + 1 < h) metadelta[x[i]][y[i] + 1] = -a[i];
			continue;
		}

		int vstart = max(0, (int) (x[i] - possible));
		int vend = min(w - 1, (int) (x[i] + possible));
		int hstart = max(0, (int) (y[i] - possible));
		int hend = min(h - 1, (int) (y[i] + possible));

		for (int j = vstart; j <= vend; j++) {
			ll initialValue = a[i] - b[i] * max(llabs(x[i] - j), llabs(hstart - y[i]));
			metadelta[j][hstart] += initialValue;
			if (hstart + 1 < h) {
				metadelta[j][hstart + 1] += -initialValue;
				{metadelta[j][hstart + 1] += b[i];}
			}

			//find the places where the delta is subtracted in the middle
			ll heightDiff = llabs(x[i] - j);
			ll spot1 = max(hstart + 1LL, y[i] - heightDiff + 1);
			ll spot2 = min(hend + 1LL, y[i] + heightDiff + 1);

			//cout << "row " << j << " spot1, spot2 are " << spot1 << ' ' << spot2 << endl;

			if (spot1 >= hstart && spot1 <= hend) metadelta[j][(int) spot1] += -b[i];
			if (spot2 >= hstart && spot2 <= hend + 1) metadelta[j][(int) spot2] += -b[i]; 

			ll finalValue = a[i] - b[i] * max(llabs(x[i] - j), llabs(hend - y[i]));
			if (hend + 1 < h) {
				metadelta[j][hend + 1] += -finalValue;
				if (hend + 2 < h) metadelta[j][hend + 2] += finalValue;
				metadelta[j][hend + 1] += b[i];
			}
		}
	}

	for (int i = 0; i < w; i++) {
		ll delta = 0;
		ll current = 0;
		for (int j = 0; j < h; j++) {
			delta += metadelta[i][j];
			current += delta;

			//cout << current << ' ';
			updateRect(i, j, i, j, current);
		}
		//cout << endl;
	}

	makeArray(0); makeArray(1); makeArray(2); makeArray(3);


	scanf("%d", &q);//cin >> q;
	for (int i = 0; i < q; i++) {
		ll x1, y1, x2, y2;
		scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);//cin >> x1 >> y1 >> x2 >> y2;
		x1--; y1--; x2--; y2--;

		if (swapped) {
			swap(x1, y1);
			swap(x2, y2);
		}

		//cout << "bounds are " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
		ll sum = getSum(x1, y1, x2, y2);

		ll cells = (x2 - x1 + 1) * (y2 - y1 + 1);

		//cout << "query " << i << " found sum " << sum << " cells " << cells << endl;

		ll remainder = sum % cells;
		if ((cells % 2 == 0 && remainder >= cells / 2) || (cells % 2 == 1 && remainder > cells / 2)) {
			printf("%lld\n", 1 + sum / cells);//cout << 1 + sum / cells << endl; 
		} else {
			printf("%lld\n", sum / cells);//cout << sum / cells << endl;
		}
	}
	return 0;
}

Compilation message

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:81:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &w, &h);
                       ^
nuclearia.cpp:82:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
nuclearia.cpp:89:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld%lld", &x[i], &y[i], &a[i], &b[i]);
                                                    ^
nuclearia.cpp:178:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);//cin >> q;
                 ^
nuclearia.cpp:181:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);//cin >> x1 >> y1 >> x2 >> y2;
                                                ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 299848 KB Output is correct
2 Correct 102 ms 104528 KB Output is correct
3 Correct 89 ms 104528 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 299848 KB Output is correct
2 Correct 109 ms 104528 KB Output is correct

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 202376 KB Output is correct
2 Incorrect 114 ms 104528 KB Output isn't correct

Subtask #4
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 207428 KB Output is correct
2 Incorrect 118 ms 104528 KB Output isn't correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 299848 KB Output is correct
2 Correct 97 ms 104528 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 182688 KB Output is correct
2 Correct 109 ms 104528 KB Output is correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 202376 KB Output is correct
2 Incorrect 117 ms 104528 KB Output isn't correct

Subtask #8
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 163148 KB Output is correct
2 Incorrect 111 ms 104528 KB Output isn't correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 299848 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 299848 KB Output is correct

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 202376 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 202356 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #13
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 205328 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 202376 KB Execution timed out
2 Halted 0 ms 0 KB -