#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 ;
}
}
int main(){
// freopen("in.txt" ,"r" , stdin ) ;
scanf("%d%d",&n,&q) ;
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]) ;
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] ) ;
}
}
Compilation message
spiral.cpp: In function 'int main()':
spiral.cpp:40: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:49: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) ;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
33424 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
33424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
33424 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
33424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
33424 KB |
Output isn't correct |
