#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
void ck(int&x){if(x<0)x+=mod;}
int add(int x,int y){ck(x);ck(y);x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){ck(x);ck(y);x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
void ckadd(int&x,int y){x=add(x,y);}
int GetCell(int x,int y){
int mx=max(abs(x),abs(y));
int ans=mul(sub(mul(2,mx),1),sub(mul(2,mx),1));
if(y==mx)ckadd(ans,add(sub(mx,x),mul(mx,2)));
else if(x==-mx)ckadd(ans,add(sub(mx,y),mul(mx,4)));
else if(y==-mx)ckadd(ans,add(x,mul(mx,7)));
else if(x==mx)ckadd(ans,add(y,mx));
return ans;
}
int sum0(int n){return n+1;}
int sum1(int n){return mul(mul(n,n+1),(mod+1)/2);}
int sum2(int n){return mul(mul(n,n+1),mul((2*n+1)%mod,mul((mod+1)/2,(mod+1)/3)));}
int sum3(int n){return mul(sum1(n),sum1(n));}
int GetSQ(int now,int dif,int n){
int T1=sum1(n);
int T2=mul(2,sum2(n));
int T3=add(add(mul(now,sum0(n)),mul(dif,sum1(n)))
,mul(4,sub(sum2(n),sum1(n))));
int T4=mul(2,add(add(mul(now,sum1(n)),mul(dif,sum2(n)))
,mul(4,sub(sum3(n),sum2(n)))));
return add(add(T1,T2),add(T3,T4));
}
int GetST(int now,int nxt,int len,int n){
int dif=nxt-now;
int T1=add(mul(now,sum0(n-1)),mul(dif,sum1(n-1)));
int T2=mul(4,sub(sum2(n-1),sum1(n-1)));
int T3=mul(n,sum1(len-1));
return add(mul(len,add(T1,T2)),T3);
}
int Ari(int now,int dif,int n){
return add(mul(now,sum0(n)),add(mul(dif,sum1(n)),mul(4,sub(sum2(n),sum1(n)))));
}
int Get(int x,int y){
int n=min(abs(x),abs(y)),ans;
if(x>=0&&y>=0){
ans=GetSQ(1,1,n);
if(abs(x)>abs(y))ckadd(ans,GetST(GetCell(y+1,0),GetCell(y+2,0),n+1,abs(x)-abs(y)));
if(abs(x)<abs(y))ckadd(ans,GetST(GetCell(x,x+1),GetCell(x,x+2),n+1,abs(y)-abs(x)));
}else if(x>=0&&y<0){
ans=add((n>0?GetSQ(2,7,n-1):0),Ari(1,7,n));
ckadd(ans,add(mul(n,GetCell(0,-n)),sum1(n)));
if(abs(x)>abs(y))ckadd(ans,GetST(GetCell(-y+1,y),GetCell(-y+2,y),n+1,abs(x)-abs(y)));
if(abs(x)<abs(y))ckadd(ans,GetST(GetCell(0,-x-1),GetCell(0,-x-2),n+1,abs(y)-abs(x)));
}else if(x<0&&y>=0){
ans=GetSQ(1,3,n);
if(abs(x)>abs(y))ckadd(ans,GetST(GetCell(-y-1,y),GetCell(-y-2,y),n+1,abs(x)-abs(y)));
if(abs(x)<abs(y))ckadd(ans,GetST(GetCell(0,-x+1),GetCell(0,-x+2),n+1,abs(y)-abs(x)));
}else if(x<0&&y<0){
ans=GetSQ(1,5,n);
if(abs(x)>abs(y))ckadd(ans,GetST(GetCell(y-1,0),GetCell(y-2,0),n+1,abs(x)-abs(y)));
if(abs(x)<abs(y))ckadd(ans,GetST(GetCell(x,x-1),GetCell(x,x-2),n+1,abs(y)-abs(x)));
}
return ans;
}
int Get(int x1,int y1,int x2,int y2){
if(x1>x2||y1>y2)return 0;
if(x1>=0&&y1>=0)return sub(add(Get(x2,y2),x1!=0&&y1!=0?Get(x1-1,y1-1):0),add(x1!=0?Get(x1-1,y2):0,y1!=0?Get(x2,y1-1):0));
if(x1<0&&y1>=0)return sub(add(Get(x1,y2),x2!=0&&y1!=0?Get(x2+1,y1-1):0),add(x2!=0?Get(x2+1,y2):0,y1!=0?Get(x1,y1-1):0));
if(x1>=0&&y1<0)return sub(add(Get(x2,y1),x1!=0&&y2!=0?Get(x1-1,y2+1):0),add(x1!=0?Get(x1-1,y1):0,y2!=0?Get(x2,y2+1):0));
if(x1<0&&y1<0)return sub(add(Get(x1,y1),x2!=0&&y2!=0?Get(x2+1,y2+1):0),add(x2!=0?Get(x2+1,y1):0,y2!=0?Get(x1,y2+1):0));
}
int main(){
int n,q;
scanf("%i %i",&n,&q);
while(q--){
int x1,y1,x2,y2;
scanf("%i %i %i %i",&x1,&y1,&x2,&y2);
int ans=add(add(Get(max(0,x1),max(0,y1),x2,y2),Get(x1,max(0,y1),min(-1,x2),y2)),add(Get(max(0,x1),y1,x2,min(-1,y2)),Get(x1,y1,min(-1,x2),min(-1,y2))));
printf("%i\n",ans);
}
return 0;
}
Compilation message
spiral.cpp: In function 'int Get(int, int, int, int)':
spiral.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
70 | }
| ^
spiral.cpp: In function 'int main()':
spiral.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%i %i",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
spiral.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
76 | scanf("%i %i %i %i",&x1,&y1,&x2,&y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
spiral.cpp: In function 'int Get(int, int)':
spiral.cpp:62:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | return ans;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
