oj.uz

Submission #259205

# Submission time Handle Problem Language Result Execution time Memory
259205 2020-08-07T11:47:31 Z Berted Nuclearia (CEOI15_nuclearia) C++14
0 / 100
 1000 ms 441064 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, ar6;

pii start[200001], C[200001];
int A[200001], B[200001];
ll ans[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()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> w >> h;

	for (int i = 0; i <= w + 1; i++)
	{
		ar.push_back(vi());
		ar2.push_back(vi());
		ar3.push_back(vi());
		ar4.push_back(vi());
		ar6.push_back(vi());
		for (int j = 0; j <= h + 1; j++)
		{
			ar.back().push_back(0);
			ar2.back().push_back(0);
			ar3.back().push_back(0);
			ar4.back().push_back(0);
			ar6.back().push_back(0);
		}
	}

	cin >> n;	

	for (int i = 0; i < n; i++)
	{
		cin >> C[i].fst >> C[i].snd >> A[i] >> B[i];
		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)};

		//cout << a.fst << " " << a.snd << "\n";
		//cout << b.fst << " " << b.snd << "\n";

		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)};

		//cout << a.fst << " " << a.snd << "\n";
		//cout << b.fst << " " << b.snd << "\n";

		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, 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]);
	}

	/*
	outputDebug(ar);
	outputDebug(ar2);
	outputDebug(ar3);
	cout << "---\n";
	*/

	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];
		}
	}
	/*
	outputDebug(ar);
	outputDebug(ar2);
	outputDebug(ar3);
	cout << "---\n";
	*/
	reset(ar3);

	for (int i = 0; i < n; i++)
	{
		int d = A[i] / B[i];
		int dst = min(d - 1, min(C[i].fst - 1, C[i].snd - 1));
		ar3[C[i].fst - dst][C[i].snd - dst] -= B[i];
		if (dst < d - 1)
		{
			if (C[i].fst - 1 < C[i].snd - 1)
			{
				ar6[0][max(0, C[i].snd - d + 1)] -= B[i];
				ar6[0][C[i].snd - dst] += B[i];
			}
		}
		dst = min(d - 1, 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[0][C[i].snd + dst] -= B[i];
				ar6[0][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[0][j] += ar6[0][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];
			ar2[i][j] += ar6[i][j];
		}
	}
	/*
	outputDebug(ar2);
	outputDebug(ar3);
	outputDebug(ar4);
	*/

	cin >> q;

	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];
			//cout << ar[i][j] << " ";
		}
		//cout << "\n";
	}

	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];
		}
	}

	for (int i = 0; i < q; i++) 
	{
		int s, l, e, r; ll sz = 0;
		cin >> s >> l >> 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1116 ms 441064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1101 ms 425632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

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

Subtask #4
0 / 2.0

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

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 429632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1121 ms 355724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

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

Subtask #8
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 182576 KB Output is correct
2 Incorrect 75 ms 4600 KB Output isn't correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1131 ms 415752 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1126 ms 435780 KB Time limit exceeded

Subtask #11
0 / 15.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 12.0

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

Subtask #14
0 / 8.0

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