oj.uz

Submission #259612

# Submission time Handle Problem Language Result Execution time Memory
259612 2020-08-08T04:15:15 Z Berted Nuclearia (CEOI15_nuclearia) C++14
100 / 100
 661 ms 261360 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>
#define ll long long
#define vi vector<ll>
#define pub push_back
#define pii pair<int, int>
#define fst first
#define snd second
#define ppi pair<pii, int>

using namespace std;

int w, h, n, q;
vector<vi> ar, ar2, ar3, ar4;
vi ar6;

pii C[200001];
int A[200001], B[200001];

inline int getDist(pii a, pii b)
{
	return max(abs(a.fst - b.fst), abs(a.snd - b.snd));
}

inline void insert(int x, int y, vector<vi>& v, ll val)
{
	if (x < 0) {x = 0;}
	if (x > w) {x = w + 1;}
	if (y < 1) {y = 1;}
	if (y > h) {y = h + 1;}
	v[x][y] += val;
}

inline void reset(vector<vi> &v)
{
	for (int i = 0; i <= w + 1; i++)
	{
		for (int j = 0; j <= h + 1; j++)
		{
			v[i][j] = 0;
		}
	}
}

inline void outputDebug(const vector<vi> &v)
{
	cout << "\n";
	for (int i = 0; i <= h + 1; i++)
	{
		for (int j = 0; j <= w + 1; j++)
		{
			cout << setw(2) << v[j][i] << " ";
		}
		cout << "\n";
	}
}

int main()
{
	bool rrr = 0;
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> w >> h;

	if (w > h) {swap(w, h); rrr = 1;}

	ar.assign(w + 2, vi(h + 2, 0));
	ar2.assign(w + 2, vi(h + 2, 0));
	ar3.assign(w + 2, vi(h + 2, 0));
	ar4.assign(w + 2, vi(h + 2, 0));
	ar6.assign(h + 2, 0);

	cin >> n;	

	for (int i = 0; i < n; i++)
	{
		cin >> C[i].fst >> C[i].snd >> A[i] >> B[i];
		if (rrr) swap(C[i].fst, C[i].snd);
		int d = A[i] / B[i];
		pii a = {max(1, C[i].fst - d), max(1, C[i].snd - d)};
		pii b = {max(1, C[i].fst - d), min(h, C[i].snd + d)};

		insert(a.fst, a.snd, ar2, B[i]);
		insert(b.fst, C[i].snd + d, ar2, -B[i]);

		insert(a.fst, a.snd, ar, A[i] - B[i] * getDist(a, C[i]));
		insert(b.fst, b.snd + 1, ar, -(A[i] - B[i] * getDist(b, C[i])));

		insert(a.fst, C[i].snd - d, ar3, B[i]);
		insert(a.fst, C[i].snd - (C[i].fst - a.fst), ar3, -B[i]);
		insert(a.fst, C[i].snd + (C[i].fst - a.fst), ar3, -B[i]);
		insert(a.fst, C[i].snd + d, ar3, B[i]);

		a = {min(w, C[i].fst + d), max(1, C[i].snd - d)};
		b = {min(w, C[i].fst + d), min(h, C[i].snd + d)};

		insert(a.fst, a.snd, ar2, B[i]);
		insert(b.fst, C[i].snd + d, ar2, -B[i]);

		insert(a.fst + 1, a.snd, ar, -(A[i] - B[i] * getDist(a, C[i])));
		insert(b.fst + 1, b.snd + 1, ar, (A[i] - B[i] * getDist(b, C[i])));

		insert(a.fst + 1, C[i].snd - d, ar3, -B[i]);
		insert(a.fst + 1, C[i].snd - (C[i].fst - a.fst), ar3, B[i]);
		insert(a.fst + 1, C[i].snd + (C[i].fst - a.fst), ar3, B[i]);
		insert(a.fst + 1, C[i].snd + d, ar3, -B[i]);
	}

	for (int i = 0; i <= w + 1; i++)
	{
		for (int j = 1; j <= h + 1; j++)
		{
			ar2[i][j] += ar2[i][j - 1];
			ar[i][j] += ar[i][j - 1] + ar3[i][j - 1];
			ar3[i][j] += ar3[i][j - 1];
		}
	}
	
	reset(ar3);

	for (int i = 0; i < n; i++)
	{
		int d = A[i] / B[i];
		int dst = min(d, min(C[i].fst - 1, C[i].snd - 1));
		ar3[C[i].fst - dst][C[i].snd - dst] -= B[i];
		if (dst < d)
		{
			if (C[i].fst - 1 < C[i].snd - 1)
			{
				ar6[max(0, C[i].snd - d)] -= B[i];
				ar6[C[i].snd - dst] += B[i];
			}
		}
		dst = min(d, min(w - C[i].fst, C[i].snd - 1));
		ar4[C[i].fst + dst][C[i].snd - dst] -= B[i];
		dst = min(d, min(w + 1 - C[i].fst, h + 1 - C[i].snd));
		ar3[C[i].fst + dst][C[i].snd + dst] += B[i];
		dst = min(d, min(C[i].fst, h + 1 - C[i].snd));
		ar4[C[i].fst - dst][C[i].snd + dst] += B[i];
		if (dst < d)
		{
			if (C[i].fst < h + 1 - C[i].snd)
			{
				ar6[C[i].snd + dst] -= B[i];
				ar6[min(h + 1, C[i].snd + d)] += B[i];
			}
		}
	}

	for (int i = 1; i <= w + 1; i++)
	{
		for (int j = 1; j <= h + 1; j++) 
		{
			ar3[i][j] += ar3[i - 1][j - 1];
		}
	}

	for (int i = w; i >= 0; i--)
	{
		for (int j = 1; j <= h + 1; j++)
		{
			ar4[i][j] += ar4[i + 1][j - 1];
		}
	}

	for (int j = 1; j <= h + 1; j++) {ar6[j] += ar6[j - 1];}

	for (int i = 0; i <= w + 1; i++)
	{
		for (int j = 0; j <= h + 1; j++)
		{
			ar2[i][j] += ar3[i][j];
			ar2[i][j] += ar4[i][j];
		}
	}
	for (int j = 0; j <= h + 1; j++) ar2[0][j] += ar6[j];

	for (int i = 0; i <= w + 1; i++)
	{
		for (int j = 0; j <= h + 1; j++)
		{
			if (i) ar[i][j] = ar[i][j] + ar[i - 1][j];
			if (i > 1) ar[i][j] = ar[i][j] + ar2[i - 1][j];
			if (i) ar2[i][j] = ar2[i - 1][j] + ar2[i][j];
		}
	}

	for (int i = 0; i <= w + 1; i++)
	{
		for (int j = 0; j <= h + 1; j++)
		{
			if (j) ar[i][j] += ar[i][j - 1];
			if (i) ar[i][j] += ar[i - 1][j];
			if (i && j) ar[i][j] -= ar[i - 1][j - 1];
		}
	}

	cin >> q;

	for (int i = 0; i < q; i++) 
	{
		int s, l, e, r; ll sz = 0;
		cin >> s >> l >> e >> r;
		if (rrr) {swap(s, l); swap(e, r);}
		sz = ((ll)(r - l + 1) * (e - s + 1));
		ll res = ar[e][r] - ar[e][l - 1] - ar[s - 1][r] + ar[s - 1][l - 1];
		if (2 * (res % sz) >= sz) cout << res / sz + 1 << "\n";
		else cout << res / sz << "\n";
	}

	return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 254852 KB Output is correct
2 Correct 88 ms 3576 KB Output is correct
3 Correct 84 ms 3064 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 254728 KB Output is correct
2 Correct 90 ms 3576 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 79096 KB Output is correct
2 Correct 84 ms 3576 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 87456 KB Output is correct
2 Correct 87 ms 3576 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 257416 KB Output is correct
2 Correct 108 ms 5560 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 104928 KB Output is correct
2 Correct 89 ms 3192 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 81912 KB Output is correct
2 Correct 90 ms 3448 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 69804 KB Output is correct
2 Correct 84 ms 3192 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 261000 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 261360 KB Output is correct

Subtask #11
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 84344 KB Output is correct
2 Correct 409 ms 84600 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 84460 KB Output is correct
2 Correct 421 ms 84224 KB Output is correct

Subtask #13
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 86104 KB Output is correct
2 Correct 362 ms 84984 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 84728 KB Output is correct
2 Correct 632 ms 260484 KB Output is correct