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

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>q;
	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
		{
			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: RUNTIME ERROR

Group: 3

Verdict: TIME LIMIT EXCEEDED

Group: 4

Verdict: RUNTIME ERROR

Group: 5

Verdict: RUNTIME ERROR