제출 #257032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
257032		maximath_1	Spiral (BOI16_spiral)	C++11	100 / 100	1 ms	384 KiB

spiral

#include <iostream>
using namespace std;

#define ll long long
const ll mod = 1e9 + 7;
ll i2 = (mod + 1) / 2ll, i3 = (mod + 1) / 3ll;

ll fI(ll x, ll y){
	ll mn = min(x, y);
	ll rs = (2ll * mn * mn % mod * (mn + 1ll) % mod * (mn + 1ll) % mod + mn + 1ll) % mod;
	if(x > y){
		ll p1 = ((mod - 3ll) * (x + y + 1ll) % mod + 2ll + y) % mod;
		p1 = (p1 * 1ll * (x - y)) % mod; p1 = (p1 * 1ll * i2) % mod;
		ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
		p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
		p2 = (p2 * i3) % mod;
		ll tp = (p1 + p2) % mod;
		tp = (tp * (y + 1ll)) % mod;
		rs = (rs + tp) % mod;
	}else{
		ll p1 = ((mod - 1ll) * (x + y + 1ll) % mod + 2ll + mod - x) % mod;
		p1 = (p1 * 1ll * (y - x)) % mod; p1 = (p1 * 1ll * i2) % mod;
		ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
		p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
		p2 = (p2 * i3) % mod;
		p2 = (mod - p2) % mod;
		ll tp = (p1 + p2) % mod;
		tp = (tp * (x + 1ll)) % mod;
		rs = (rs + tp) % mod;
	}
	return rs;
}

ll fII(ll x, ll y){
	x *= -1ll;
	ll mn = min(x, y);
	ll rs = (2ll * mn * mn % mod * (mn + 1ll) % mod * (mn + 1ll) % mod) % mod;
	(rs += (2ll * mn * (mn + 1ll) % mod * (2ll * mn + 1ll) % mod) * i3 % mod) %= mod;
	rs = (rs + mn * (mn + 1ll) % mod + mn + 1ll) % mod;
	if(x > y){
		ll p1 = ((1ll) * (x + y + 1ll) % mod + 2ll + mod - y) % mod;
		p1 = (p1 * 1ll * (x - y)) % mod; p1 = (p1 * 1ll * i2) % mod;
		ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
		p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
		p2 = (p2 * i3) % mod;
		ll tp = (p1 + p2) % mod;
		tp = (tp * (y + 1ll)) % mod;
		rs = (rs + tp) % mod;
	}else{
		ll p1 = ((mod - 1ll) * (x + y + 1ll) % mod + 2ll + x) % mod;
		p1 = (p1 * 1ll * (y - x)) % mod; p1 = (p1 * 1ll * i2) % mod;
		ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
		p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
		p2 = (p2 * i3) % mod;
		p2 = (mod - p2) % mod;
		ll tp = (p1 + p2) % mod;
		tp = (tp * (x + 1ll)) % mod;
		rs = (rs + tp) % mod;
	}
	return rs;
}

ll fIII(ll x, ll y){
	x *= -1ll; y *= -1ll;
	ll mn = min(x, y);
	ll rs = (2ll * mn * mn % mod * (mn + 1ll) % mod * (mn + 1ll) % mod) % mod;
	(rs += (4ll * mn * (mn + 1ll) % mod * (2ll * mn + 1ll) % mod) * i3 % mod) %= mod;
	rs = (rs + (2ll * mn + 1ll) * 1ll * (mn + 1ll) % mod) % mod;
	if(x > y){
		ll p1 = ((1ll) * (x + y + 1ll) % mod + 2ll + y) % mod;
		p1 = (p1 * 1ll * (x - y)) % mod; p1 = (p1 * 1ll * i2) % mod;
		ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
		p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
		p2 = (p2 * i3) % mod;
		ll tp = (p1 + p2) % mod;
		tp = (tp * (y + 1ll)) % mod;
		rs = (rs + tp) % mod;
	}else{
		ll p1 = ((3ll) * (x + y + 1ll) % mod + 2ll + mod - x) % mod;
		p1 = (p1 * 1ll * (y - x)) % mod; p1 = (p1 * 1ll * i2) % mod;
		ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
		p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
		p2 = (p2 * i3) % mod;
		p2 = (mod - p2) % mod;
		ll tp = (p1 + p2) % mod;
		tp = (tp * (x + 1ll)) % mod;
		rs = (rs + tp) % mod;
	}
	return rs;
}

ll fIV(ll x, ll y){
	y *= -1ll;
	ll mn = min(x, y);
	ll rs = (2ll * mn * mn % mod * (mn + 1ll) % mod * (mn + 1ll) % mod) % mod;
	(rs += (2ll * mn * (mn + 1ll) % mod * (2ll * mn + 1ll) % mod) * i3 % mod) %= mod;
	rs = (rs + (mn + 1ll) * 1ll * (3ll * mn + 1ll) % mod) % mod;
	if(x > y){
		ll p1 = ((mod - 3ll) * (x + y + 1ll) % mod + 2ll + mod - y) % mod;
		p1 = (p1 * 1ll * (x - y)) % mod; p1 = (p1 * 1ll * i2) % mod;
		ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
		p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
		p2 = (p2 * i3) % mod;
		ll tp = (p1 + p2) % mod;
		tp = (tp * (y + 1ll)) % mod;
		rs = (rs + tp) % mod;
	}else{
		ll p1 = ((3ll) * (x + y + 1ll) % mod + 2ll + x) % mod;
		p1 = (p1 * 1ll * (y - x)) % mod; p1 = (p1 * 1ll * i2) % mod;
		ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
		p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
		p2 = (p2 * i3) % mod;
		p2 = (mod - p2) % mod;
		ll tp = (p1 + p2) % mod;
		tp = (tp * (x + 1ll)) % mod;
		rs = (rs + tp) % mod;
	}
	return rs;
}

ll rsI(ll x1, ll x2, ll y1, ll y2){
	if(x1 > x2 || y1 > y2) return 0ll;
	ll ans = fI(x2, y2);
	if(x1) ans = (ans + mod - fI(x1 - 1, y2)) % mod;
	if(y1) ans = (ans + mod - fI(x2, y1 - 1)) % mod;
	if(x1 && y1) ans = (ans + fI(x1 - 1, y1 - 1)) % mod;
	return ans;
}

ll rsII(ll x1, ll x2, ll y1, ll y2){
	if(x1 > x2 || y1 > y2) return 0ll;
	ll ans = fII(x1, y2);
	if(x2) ans = (ans + mod - fII(x2 + 1ll, y2)) % mod;
	if(y1) ans = (ans + mod - fII(x1, y1 - 1ll)) % mod;
	if(x2 && y1) ans = (ans + fII(x2 + 1ll, y1 - 1ll)) % mod;
	return ans;
}

ll rsIII(ll x1, ll x2, ll y1, ll y2){
	if(x1 > x2 || y1 > y2) return 0ll;
	ll ans = fIII(x1, y1);
	if(x2) ans = (ans + mod - fIII(x2 + 1ll, y1)) % mod;
	if(y2) ans = (ans + mod - fIII(x1, y2 + 1ll)) % mod;
	if(x2 && y2) ans = (ans + fIII(x2 + 1ll, y2 + 1ll)) % mod;
	return ans;
}

ll rsIV(ll x1, ll x2, ll y1, ll y2){
	if(x1 > x2 || y1 > y2) return 0ll;
	ll ans = fIV(x2, y1);
	if(x1) ans = (ans + mod - fIV(x1 - 1ll, y1)) % mod;
	if(y2) ans = (ans + mod - fIV(x2, y2 + 1ll)) % mod;
	if(x1 && y2) ans = (ans + fIV(x1 - 1ll, y2 + 1ll)) % mod;
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

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

	for(ll x1, y1, x2, y2; q --;){
		cin >> x1 >> y1 >> x2 >> y2;

		ll ansI = rsI(max(x1, 0ll), min(x2, 1000000000ll), max(y1, 0ll), min(y2, 1000000000ll));
		ll ansII = rsII(max(x1, -1000000000ll), min(x2, -1ll), max(y1, 0ll), min(y2, 1000000000ll));
		ll ansIII = rsIII(max(x1, -1000000000ll), min(x2, -1ll), max(y1, -1000000000ll), min(y2, -1ll));
		ll ansIV = rsIV(max(x1, 0ll), min(x2, 1000000000ll), max(y1, -1000000000ll), min(y2, -1ll));

		ll ans = (ansI + ansII) % mod;
		ans = (ans + ansIII) % mod;
		ans = (ans + ansIV) % mod;
		cout << ans << endl;
	}

	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25