#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define ii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vii vector<ii>
inline ll sqr(ll x) { return x*x ; }
const ll mod = 1e9 + 7 ;
int n , q ;
ll qs[2005][2005] ;
int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , -1 , 0 , 1} ;
void fill_table(int x , int y , ll k ){
qs[y+n+1][x+n+1] = k ;
if( x == -y && sqr(2*abs(x)+1) == k ){
if(x == n) return ;
fill_table(x+1 , y , k+1 );
return ;
}
if( sqr(2*(max( abs(x),abs(y))-1) + 1) == k-1 ){
fill_table(x , y+1 , k+1) ;
return ;
}
int nx , ny ;
for(int i=0;i<4;i++){
nx = x + dx[i] ; ny = y + dy[i] ;
if(qs[ny + n + 1][nx + n + 1] > 0 ) continue ;
if( max(abs(nx) , abs(ny)) != max( abs(x),abs(y)) ) continue ;
fill_table(nx , ny , k+1) ;
return ;
}
}
ll find_ans(int x , int y){
int mx = max(abs(x) , abs(y) ) ;
ll res = sqr(2*mx + 1)%mod ;
if(x == mx && y == -mx) return sqr(2*x+1) ;
if(abs(x) == mx){
if(x > 0) return res - 8*mx + y + mx + 1 ;
else return res - 2*mx - y - mx ;
}
else{
if(y > 0) return res - 4*mx - x - mx ;
else return res + x - mx ;
}
}
int main(){
// freopen("in.txt" ,"r" , stdin ) ;
scanf("%d%d",&n,&q) ;
if(n <= 1000){
fill_table(0 , 0 , 1) ;
/*for(int i=1;i<=2*n+1;i++) {
for(int j=1;j<=2*n+1;j++) printf("%lld " , qs[i][j]) ;
cout<<endl;
}*/
for(int i=1;i<=2*n+1;i++)
for(int j=1;j<=2*n+1;j++) qs[i][j] += (qs[i][j-1] + qs[i-1][j] - qs[i-1][j-1]) ,
qs[i][j]%=mod ;
int x1 , x2 , y1 , y2 ;
for(int i=0 ; i<q ; i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ;
x1 += n+1 ; y1 += n+1 ; x2 += n+1 ; y2 += n+1 ;
printf("%lld\n" , ( (qs[y2][x2] - qs[y2][x1-1] - qs[y1-1][x2] + qs[y1-1][x1-1])%mod + mod )%mod ) ;
}
return 0 ;
}
int x1 , x2 , y1 , y2 ;
for(int i=0 ; i<q ; i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ;
printf("%lld\n" , ( find_ans(x1,y1)+mod)%mod ) ;
}
}
Compilation message
spiral.cpp: In function 'int main()':
spiral.cpp:54:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q) ;
^
spiral.cpp:66:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ;
^
spiral.cpp:74:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
143 ms |
33424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
33424 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
143 ms |
33424 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
33424 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
33424 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
143 ms |
33424 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
33424 KB |
Output isn't correct |
