oj.uz

Submission #739100

# Submission time Handle Problem Language Result Execution time Memory
739100 2023-05-09T23:47:56 Z Charizard2021 Spiral (BOI16_spiral) C++17
100 / 100
 1 ms 324 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int Z;

constexpr Z mod = 1000000007;

struct M {
	M() : x(0) { }
	M(Z s) {
		x = s % mod;
		if(x < 0) x += mod;
	}

	Z x;
};
M operator+(M a, M b) {
	return M(a.x + b.x);
}
M operator-(M a, M b) {
	return M(a.x - b.x);
}
M operator-(M a) {
	return M(-a.x);
}
M operator*(M a, M b) {
	return M(a.x * b.x);
}

M arithSum(Z a, Z b) {
	return (b * (b + 1) - a * (a - 1)) / 2;
}

M clampArithSum(int a1, int b1, int a2, int b2, M c) {
	int a = max(a1, a2);
	int b = min(b1, b2);
	if(a <= b) {
		return arithSum(a, b) + (b - a + 1) * c;
	} else {
		return 0;
	}
}

bool bw(int a, int x, int b) {
	return a <= x && x <= b;
}

M layerSum(int l, int x1, int y1, int x2, int y2) {
	if(l == 0) {
		if(x1 <= 0 && x2 >= 0 && y1 <= 0 && y2 >= 0) {
			return 1;
		} else {
			return 0;
		}
	}

	Z val = (Z)(2 * l + 1) * (Z)(2 * l + 1);
	M ret;

	val = val - l;
	if(bw(y1, -l, y2)) ret = ret + clampArithSum(-l, l, x1, x2, val);
	val = val - 2 * l;
	if(bw(x1, -l, x2)) ret = ret + clampArithSum(-l + 1, l - 1, -y2, -y1, val);
	val = val - 2 * l;
	if(bw(y1, l, y2)) ret = ret + clampArithSum(-l, l, -x2, -x1, val);
	val = val - 2 * l;
	if(bw(x1, l, x2)) ret = ret + clampArithSum(-l + 1, l - 1, y1, y2, val);

	return ret;
}

M div2((mod + 1) / 2);
M div6((mod + 1) / 6);

int main() {
	cin.sync_with_stdio(false);
	cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	for(int i = 0; i < q; ++i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		vector<int> events;
		events.push_back(0);
		events.push_back(1);
		events.push_back(2);
		events.push_back(std::abs(x1) - 1);
		events.push_back(std::abs(x1));
		events.push_back(std::abs(x1) + 1);
		events.push_back(std::abs(x2) - 1);
		events.push_back(std::abs(x2));
		events.push_back(std::abs(x2) + 1);
		events.push_back(std::abs(y1) - 1);
		events.push_back(std::abs(y1));
		events.push_back(std::abs(y1) + 1);
		events.push_back(std::abs(y2) - 1);
		events.push_back(std::abs(y2));
		events.push_back(std::abs(y2) + 1);
		sort(events.begin(), events.end());

		M ret;
		for(int i = 1; i < (int)events.size(); ++i) {
			int a = events[i - 1];
			int b = events[i];
			if(a < 0 || a == b) continue;
			int k = b - a;
			if(k >= 4) {
				M v[4];
				for(int j = 0; j < 4; ++j) {
					v[j] = layerSum(a + j, x1, y1, x2, y2);
				}
				M A = (v[3] - 2 * v[2] + v[1]) - (v[2] - 2 * v[1] + v[0]);
				A = A * div6;
				v[1] = v[1] - A;
				v[2] = v[2] - 8 * A;
				v[3] = v[3] - 27 * A;
				M B = v[2] - 2 * v[1] + v[0];
				B = B * div2;
				v[1] = v[1] - B;
				v[2] = v[2] - 4 * B;
				v[3] = v[3] - 9 * B;
				M C = v[1] - v[0];
				M D = v[0];

				M K = k;
				M H = K * (K - 1) * div2;
				ret = ret + H * H * A;
				ret = ret + K * (K - 1) * (2 * K - 1) * div6 * B;
				ret = ret + H * C;
				ret = ret + K * D;
			} else {
				for(int l = a; l < b; ++l) {
					ret = ret + layerSum(l, x1, y1, x2, y2);
				}
			}
		}

		cout << ret.x << '\n';
	}

	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 244 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 244 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct