Submission #259612

#	Time	Username	Problem	Language	Result	Execution time	Memory
259612		Berted	Nuclearia (CEOI15_nuclearia)	C++14	100 / 100	661 ms	261360 KiB

nuclearia

#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 / 3
• Subtask 2: 2 / 2
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 6 / 6
• Subtask 6: 4 / 4
• Subtask 7: 6 / 6
• Subtask 8: 4 / 4
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10
• Subtask 11: 15 / 15
• Subtask 12: 10 / 10
• Subtask 13: 12 / 12
• Subtask 14: 8 / 8