oj.uz

Submission #741178

# Submission time Handle Problem Language Result Execution time Memory
741178 2023-05-13T18:54:48 Z Charizard2021 Spiral (BOI16_spiral) C++17
100 / 100
 1 ms 300 KB 
#include<bits/stdc++.h>
using namespace std;
constexpr long long int mod = 1000000007;

struct MOD {
	MOD() : x(0) { }
	MOD(long long int s) {
		x = s % mod;
		if(x < 0) x += mod;
	}

	long long int x;
};
MOD operator+(MOD a, MOD b) {
	return MOD(a.x + b.x);
}
MOD operator-(MOD a, MOD b) {
	return MOD(a.x - b.x);
}
MOD operator-(MOD a) {
	return MOD(-a.x);
}
MOD operator*(MOD a, MOD b) {
	return MOD(a.x * b.x);
}

MOD arithSum(long long int a, long long int b) {
	return (b * (b + 1) - a * (a - 1)) / 2;
}

MOD clampArithSum(int a1, int b1, int a2, int b2, MOD 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;
}

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

	long long int val = (long long int)(2 * l + 1) * (long long int)(2 * l + 1);
	MOD 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;
}
MOD div2((mod + 1) / 2);
MOD div6((mod + 1) / 6);
int main() {
	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(abs(x1) - 1);
		events.push_back(abs(x1));
		events.push_back(abs(x1) + 1);
		events.push_back(abs(x2) - 1);
		events.push_back(abs(x2));
		events.push_back(abs(x2) + 1);
		events.push_back(abs(y1) - 1);
		events.push_back(abs(y1));
		events.push_back(abs(y1) + 1);
		events.push_back(abs(y2) - 1);
		events.push_back(abs(y2));
		events.push_back(abs(y2) + 1);
		sort(events.begin(), events.end());

		MOD 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) {
				MOD v[4];
				for(int j = 0; j < 4; ++j) {
					v[j] = layerSum(a + j, x1, y1, x2, y2);
				}
				MOD 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;
				MOD 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;
				MOD C = v[1] - v[0];
				MOD D = v[0];

				MOD K = k;
				MOD 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 212 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 1 ms 296 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 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 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct