Code Submission Evaluation System

Login

Tasks | Scoreboard | Statistics

Feedback

Test results

Compiler report

input/code.cpp: In function 'll singlesquare(ll, ll)':
input/code.cpp:75:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  res %= MOD;
            ^

Code

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef pair<ii, ll> iii;

const int MOD = 1e9 + 7;

ll abso(ll y)
{
	if(y < 0) return -y;
	return y;
}
ll n, q; 
ll dp[2011][2011];
ll spiral[2011][2011];

ll singlesquare(ll x, ll y)
{
	ll res;
	if(x == 0 && y == 0) return 1;
	if(x == 0 && y > 0)
	{
		res = 4*y*y - y + 1;
	}
	else if(x == 0 && y < 0)
	{
		res = 4*y*y - 3*y + 1;
	}
	else if(x > 0 && y == 0)
	{
		res = 4*x*x - 3*x + 1;
	}
	else if(x < 0 && y == 0)
	{
		res = 4*x*x - x + 1;
	}
	else
	{
		ll layer = max(abso(x), abso(y));
		if(abso(y) == layer)
		{
			res = singlesquare(0, y);
			//cout << res << endl;
			if(y > 0)
			{
				res -= x;
			}
			else
			{
				res += x;
			}
		}
		else if(abso(x) == layer)
		{
			res = singlesquare(x, 0);
			if(x > 0)
			{
				res += y;
			}
			else
			{
				res -= y;
			}
		}
	}
	res %= MOD;
	if(res < 0) res += MOD;
	return res;
}

void fillspiral()
{
	for(int i = 1; i <= 2*n + 1; i++)
	{
		for(int j = 1; j <= 2*n + 1; j++)
		{
			spiral[i][j] = singlesquare(i - n - 1, j - n - 1);
		}
	}
	/*
	for(int i = 2*n + 1; i >= 1; i--)
	{
		for(int j = 1; j <= 2*n + 1; j++)
		{
			cout << spiral[j][i] << ' ';
		}
		cout << '\n';
	}
	*/
}

void filldp()
{
	for(int i = 1; i <= 2*n + 1; i++)
	{
		for(int j = 1; j <= 2*n + 1; j++)
		{
			if(i == 1 && j == 1) dp[i][j] = spiral[i][j];
			else if(i == 1)
			{
				dp[i][j] = (dp[i][j - 1] + spiral[i][j])%MOD;
			}
			else if(j == 1)
			{
				dp[i][j] = (dp[i - 1][j] + spiral[i][j])%MOD;
			}
			else
			{
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + spiral[i][j])%MOD;
				if(dp[i][j] < 0) dp[i][j] += MOD;
			}
		}
	}
	/*
	for(int i = 2*n + 1; i >= 1; i--)
	{
		for(int j = 1; j <= 2*n + 1; j++)
		{
			cout << dp[j][i] << ' ';
		}
		cout << '\n';
	}
	*/
}

ll rec(ll x1, ll y1, ll x2, ll y2)
{
	ll res = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
	res %= MOD;
	if(res < 0) res += MOD;
	return res;
}

ll modpow(ll a, ll b)
{
	ll r = 1;
	while(b)
	{
		if(b&1) r = (r*a)%MOD;
		a = (a*a)%MOD;
		b >>= 1;
	}
	if(r < 0) r += MOD;
	return r;
}

ll inv(ll x)
{
	return modpow(x, MOD - 2);
}

ll inv2, inv6, inv12;

ll mult(ll a, ll b)
{
	a %= MOD; b %= MOD;
	if(a < 0) a += MOD;
	if(b < 0) b += MOD;
	ll ans = (a*b)%MOD;
	if(ans < 0) ans += MOD;
	return ans;
}

ll sum(ll x)
{
	ll res = mult(x, mult(x + 1, inv2));
	return res;
}

ll sum2(ll x)
{
	ll res = mult(x, mult(x + 1, mult(2*x + 1, inv6)));
	return res;
}

ll sum3(ll x)
{
	ll res = mult(x, mult(x - 1, mult(x + 1, inv6)));
	return res;
}

ll sum4(ll x)
{
	ll res = mult(x, mult(x, mult(x - 1, mult(x + 1, inv12))));
	return res;
}

ll sub4(ll x, ll y)
{
	ll res = 0;
	ll a, b, c;
	if(y <= x)
	{
		c = (mult(sum(y + 1) - 1, x) + sum3(y))%MOD;
		b = (mult(sum(x), y) + sum3(y))%MOD;
		a = (mult(sum2(x), y) + sum4(y) + mult(2LL, sum3(y)))%MOD;
	}
	else
	{
		c = (mult(sum(x + 1) - 1, x) + sum3(x))%MOD;
		b = (mult(sum(x), x) + sum3(x))%MOD;
		a = (mult(sum2(x), x) + sum4(x) + mult(2LL, sum3(x)))%MOD;
		ll a2, b2, c2;
		c2 = (mult(mult(sum(y) - sum(x), x), 2LL) - mult(y - x, sum(x - 1)))%MOD;
		b2 = mult(sum(y) - sum(x), x);
		a2 = mult(sum2(y) - sum2(x), x);
		c = (c + c2)%MOD;
		b = (b + b2)%MOD;
		a = (a + a2)%MOD;
	}
	//cout << a << ' ' << b << ' ' << c << '\n';
	res = mult(a, 4LL) - mult(b, 3LL) + c;
	res %= MOD;
	if(res < 0) res += MOD;
	return res;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>q;
	inv2 = inv(2);
	inv6 = inv(6);
	inv12 = inv(12);
	if(n <= 1000)
	{
		fillspiral();
		filldp();
	}
	for(int i = 0; i < q; i++)
	{
		ll x1, x2, y1, y2;
		cin>>x1>>y1>>x2>>y2;
		if(x1 == x2 && y1 == y2) cout << singlesquare(x1,y1) << '\n';
		else if(n > 1000)
		{
			cout << sub4(x2, y2) << '\n';
		}
		else
		{
			x1 += (n+1);
			y1 += (n+1);
			x2 += (n+1);
			y2 += (n+1);
			cout << rec(x1, y1, x2, y2) << '\n';
		}
	}
	return 0;
}

Test details

Group: 1

Verdict: ACCEPTED

Group: 2

Verdict: ACCEPTED

Group: 3

Verdict: WRONG ANSWER

Group: 4

Verdict: WRONG ANSWER

Group: 5

Verdict: WRONG ANSWER