/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define int long long
using namespace std;
const int maxn = 5e3 + 10, Maxn = 1e5 + 10, SQ = 360 , lg = 22 ;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 10;
int a[maxn][maxn] , dp[maxn][maxn];
int n , like;
bool vis[maxn][maxn];
bool check(int x , int y){
return x < n && x >= 0 && y < n && y >= 0;
}
pair<int , int> ce(int x , int y){
if(like == 0){
if(check(x - 1 , y) && vis[x - 1][y] == 0){
like++;
like = like % 4;
return {x - 1 , y};
}else{
if(check(x , y + 1) && vis[x][y + 1] == 0)
return {x , y + 1};
else
return {-1 , -1};
}
}
if(like == 1){
if(check(x , y - 1) && vis[x][y - 1] == 0){
like++;
like = like % 4;
return {x , y - 1};
}else{
if(check(x - 1, y) && vis[x - 1][y] == 0)
return {x - 1, y};
else
return {-1 , -1};
}
}
if(like == 2){
if(check(x + 1 , y) && vis[x + 1][y] == 0){
like++;
like = like % 4;
return {x + 1, y};
}else{
if(check(x , y - 1) && vis[x][y - 1] == 0)
return {x, y - 1};
else
return {-1 , -1};
}
}
if(like == 3){
if(check(x , y + 1) && vis[x][y + 1] == 0){
like++;
like = like % 4;
return {x , y + 1};
}else{
if(check(x + 1, y) && vis[x + 1][y] == 0)
return {x + 1, y};
else
return {-1 , -1};
}
}
return {-1 , -1};
}
void construct(){
int i = (n - 1)/2 , j = (n - 1)/2;
int pt = 1;
a[i][j] = 1;
like = 1;
vis[i][j] = true;
j++;
pair<int , int>z;
while(true){
pt++;
vis[i][j] = 1;
a[i][j] = pt;
z = ce(i , j);
if(z.first == -1)
return;
i = z.first;
j = z.second;
}
}
void PG(){
dp[0][0] = a[0][0];
for(int i = 1 ; i < n ; i++){
dp[i][0] = (dp[i - 1][0] + a[i][0]) % mod;
dp[0][i] = (dp[0][i - 1] + a[0][i]) % mod;
}
for(int i = 1 ; i < n ; i++)
for(int j = 1 ; j < n ; j++)
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + a[i][j]) % mod;
}
int32_t main(){
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int q;
cin >> n >> q;
int nn = n;
n = 2 * n + 1;
construct();
map<int , int>mpx , mpy;
int pt = nn;
for(int i = 0 ; i <= nn ; i++){
mpx[i] = pt;
pt--;
}
pt = nn + 1;
for(int i = -1 ; i >= -1 * nn ; i--){
mpx[i] = pt;
pt++;
}
pt = 0;
for(int i = -1 * nn ; i <= -1 ; i++){
mpy[i] = pt;
pt++;
}
for(int i = 0 ; i <= nn ; i++){
mpy[i] = pt;
pt++;
}
PG();
while(q--){
int x1 , x2 , y1 ,y2;
cin >> y2 >> x2 >> y1 >> x1;
y2 = mpy[y2];
y1 = mpy[y1];
x1 = mpx[x1];
x2 = mpx[x2];
int x3 = x2;
int y3 = y1;
int ans = (dp[x3][y3] + dp[x1 - 1][y2 - 1]) % mod;
int xxx = (dp[x2][y2 - 1] + dp[x1 - 1][y1]) % mod;
ans = (ans - xxx + mod) % mod;
cout << ans << endl;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
152 ms |
89304 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
152 ms |
89304 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
152 ms |
89304 KB |
Output isn't correct |
