#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
ll rev(ll x){
ll p = mod-2;
ll r = 1;
while(p){
if(p&1) r=r*x%mod;
x=x*x%mod;
p>>=1;
}
return r;
}
struct l{
ll x;
l():x(0){}
l(const ll &y):x((y+mod)%mod){}
l(const int &y):x(((ll)y+mod)%mod){}
l operator+(const l &o)const{
return l(x+o.x);
}
l operator-(const l &o)const{
return l(x-o.x);
}
l operator*(const l &o)const{
return l(x*o.x);
}
l operator/(const l &o)const{
return l(x*rev(o.x));
}
l operator+(const int &o)const{
return l(x+o);
}
l operator-(const int &o)const{
return l(x-o);
}
l operator*(const int &o)const{
return l(x*o);
}
l operator/(const int &o)const{
return l(x*rev(o));
}
operator ll() const{
return x;
}
};
l func(l n, const vector<l> v){
l ret = 0;
l div = 1;
l m = 1;
for(ll i = 0;i<v.size();i++){
m = m*(n-i);
div = div*(i+1);
//cout << v[i] << "*" << m << "/" << div << "\n";
ret = ret+m*v[i]/div;
}
return ret;
}
l line(l n, l add){ // right 1 up 3 left 5 down 7
//cerr << "line " << n << " " << add << endl;
return func(n,{1,add,8});//n*(n-1)*(n-2)*8/6+n+n*(n-1)*add/2;
}
l grid(l w, l h){
return h*w*(w-1)/2;
}
ll get(ll x, ll y){
ll h = max(abs(x),abs(y));
ll cur = (h*2+1)*(h*2+1);
if(y==-h) cur -= h-x;
else if (x==-h) cur -= h*2+h+y;
else if (y==h) cur -= h*4+h+x;
else cur -= h*6+h-y;
return cur;
}
/*
++ 1, 8, 48, 48
+- 1, 18, 56, 48
-+ 1, 14, 56, 48
-- 1, 20, 64, 48
*/
l rightup(ll x, ll y){
//cerr << "rightup " << x << " " << y << endl;
l h = min(x,y);
l ret = func(h,{1, 8, 48, 48});
if (x>y){
ret = ret+(line(x,1)-line(h,1))*h+grid(h,x-h);
}
if(y>x){
ret = ret+(line(y,3)-line(h,3))*h-grid(h,y-h);
}
return ret;
}
l rightdown(ll x, ll y){
//cerr << "rightup " << x << " " << y << endl;
l h = min(x,y);
l ret = func(h,{1, 18, 56, 48});
if (x>y){
ret = ret+(line(x,1)-line(h,1))*h-grid(h,x-h);
}
if(y>x){
ret = ret+(line(y,7)-line(h,7))*h+grid(h,y-h);
}
return ret;
}
l leftup(ll x, ll y){
//cerr << "rightup " << x << " " << y << endl;
l h = min(x,y);
l ret = func(h,{1, 14, 56, 48});
if (x>y){
ret = ret+(line(x,5)-line(h,5))*h-grid(h,x-h);
}
if(y>x){
ret = ret+(line(y,3)-line(h,3))*h+grid(h,y-h);
}
return ret;
}
l leftdown(ll x, ll y){
//cerr << "rightup " << x << " " << y << endl;
l h = min(x,y);
l ret = func(h,{1, 20, 64, 48});
if (x>y){
ret = ret+(line(x,5)-line(h,5))*h+grid(h,x-h);
}
if(y>x){
ret = ret+(line(y,7)-line(h,7))*h-grid(h,y-h);
}
return ret;
}
l solve(const function<l(ll,ll)> &f, ll x1, ll x2, ll y1, ll y2){
l ret = f(x2,y2)+f(x1-1,y1-1)-f(x2,y1-1)-f(x1-1,y2);
//cout << "add " << ret << "\n";
return ret;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n,q;
cin >> n >> q;
/*
cout << line(2,1) << " " << line(3,1) << "\n";
cout << line(2,3) << " " << line(3,3) << "\n";
cout << line(2,5) << " " << line(3,5) << "\n";
cout << line(2,7) << " " << line(3,7) << "\n";
for(ll y = n;y>=-n;y--){
for(ll x = -n;x<=n;x++){
ll cur = get(x,y);
cout << (cur<10?"0":"") << cur << " \n"[x==n];
}
}
for(ll k = 0;k<=n;k++){
ll sum = 0;
for(ll x = 0;x<=k;x++) for(ll y = 0;y<=k;y++) sum+=get(x,y);
cout << sum << " \n"[k==n];
}
for(ll k = 0;k<=n;k++){
ll sum = 0;
for(ll x = 0;x<=k;x++) for(ll y = 0;y<=k;y++) sum+=get(x,-y);
cout << sum << " \n"[k==n];
}
for(ll k = 0;k<=n;k++){
ll sum = 0;
for(ll x = 0;x<=k;x++) for(ll y = 0;y<=k;y++) sum+=get(-x,y);
cout << sum << " \n"[k==n];
}
for(ll k = 0;k<=n;k++){
ll sum = 0;
for(ll x = 0;x<=k;x++) for(ll y = 0;y<=k;y++) sum+=get(-x,-y);
cout << sum << " \n"[k==n];
}
for(ll i = 1;i<=n;i++){
for(ll j = 1;j<=n;j++){
cout << leftdown(j,i) << " \n"[j==n];
}
}
*/
while(q--){
ll x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
l ans = 0;
if(x1>=0){
if(y1>=0){
ans = ans+solve(rightup,x1+1,x2+1,y1+1,y2+1);
}else if(y2<=0){
ans = ans+solve(rightdown,x1+1,x2+1,-y2+1,-y1+1);
}else{
ans = ans+solve(rightup,x1+1,x2+1,2,y2+1);
ans = ans+solve(rightdown,x1+1,x2+1,1,-y1+1);
}
}else if(x2<=0){
if(y1>=0){
ans = ans+solve(leftup,-x2+1,-x1+1,y1+1,y2+1);
}else if(y2<=0){
ans = ans+solve(leftdown,-x2+1,-x1+1,-y2+1,-y1+1);
}else{
ans = ans+solve(leftup,-x2+1,-x1+1,2,y2+1);
ans = ans+solve(leftdown,-x2+1,-x1+1,1,-y1+1);
}
}else{
if(y1>=0){
ans = ans+solve(rightup,2,x2+1,y1+1,y2+1);
ans = ans+solve(leftup,1,-x1+1,y1+1,y2+1);
}else if(y2<=0){
ans = ans+solve(rightdown,2,x2+1,-y2+1,-y1+1);
ans = ans+solve(leftdown,1,-x1+1,-y2+1,-y1+1);
}else{
ans = ans+solve(rightup,2,x2+1,2,y2+1);
ans = ans+solve(rightdown,2,x2+1,1,-y1+1);
ans = ans+solve(leftup,1,-x1+1,2,y2+1);
ans = ans+solve(leftdown,1,-x1+1,1,-y1+1);
}
}
cout << ans << "\n";
}
}
Compilation message
spiral.cpp: In function 'l func(l, std::vector<l>)':
spiral.cpp:52:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<l>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(ll i = 0;i<v.size();i++){
| ~^~~~~~~~~
spiral.cpp:53:18: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
53 | m = m*(n-i);
| ^
spiral.cpp:35:7: note: candidate 1: 'l l::operator-(const int&) const'
35 | l operator-(const int &o)const{
| ^~~~~~~~
spiral.cpp:53:18: note: candidate 2: 'operator-(ll {aka long long int}, ll {aka long long int})' (built-in)
53 | m = m*(n-i);
| ^
spiral.cpp:54:23: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
54 | div = div*(i+1);
| ^
spiral.cpp:38:7: note: candidate 1: 'l l::operator*(const int&) const'
38 | l operator*(const int &o)const{
| ^~~~~~~~
spiral.cpp:54:23: note: candidate 2: 'operator*(ll {aka long long int}, ll {aka long long int})' (built-in)
54 | div = div*(i+1);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
356 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
356 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
344 KB |
Output is correct |
