| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 98176 | maruii | Spiral (BOI16_spiral) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int f(int x, int y){
long long ret;
if(x>=0 && y>=0){
long long t = min(x, y);
ret = (2ll*t%mod*t%mod*(t+1)%mod*(t+1)%mod+t+1)%mod;
if(x>y) ret += (((mod-3ll)*(x+y+1)%mod+2+y)%mod*500000004%mod*(x-y)%mod+(2ll*x%mod*(x+1)%mod*(2*x+1)%mod-2ll*y%mod*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(y+1)%mod;
else ret += (((mod-1ll)*(x+y+1)%mod+2-x)%mod*500000004%mod*(y-x)%mod+(-2ll*x%mod*(x+1)%mod*(2*x+1)%mod+2ll*y%mod*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(x+1)%mod;
}
else if(y>=0){
x = -x;
long lnog t = min(x, y);
ret = (2ll*t%mod*t%mod*(t+1)%mod*(t+1)%mod+2ll*t%mod*(t+1)%mod*(2*t+1)%mod*333333336%mod+1ll*t*(t+1)%mod+t+1)%mod;
if(x>y) ret += ((1ll*(x+y+1)+2-y)%mod*500000004%mod*(x-y)%mod+(2ll*x%mod*(x+1)%mod*(2*x+1)%mod-2ll*y%mod*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(y+1)%mod;
else ret += (((mod-1ll)*(x+y+1)%mod+2+x)%mod*500000004%mod*(y-x)%mod+(-2ll*x%mod*(x+1)%mod*(2*x+1)%mod+2ll*y%mod*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(x+1)%mod;
}
else if(x>=0){
y = -y;
long long t = min(x, y);
ret = (2ll*t%mod*t%mod*(t+1)%mod*(t+1)%mod+2ll*t%mod*(t+1)%mod*(2*t+1)%mod*333333336%mod+1ll*(t+1)*(3*t+1)%mod)%mod;
if(x>y) ret += (((mod-3ll)*(x+y+1)%mod+2-y)%mod*500000004%mod*(x-y)%mod+(2ll*x%mod*(x+1)%mod*(2*x+1)%mod-2ll*y%mod*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(y+1)%mod;
else ret += ((3ll*(x+y+1)+2+x)%mod*500000004%mod*(y-x)%mod+(-2ll*x%mod*(x+1)%mod*(2*x+1)%mod+2ll*y%mod*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(x+1)%mod;
}
else{
x = -x, y = -y;
long long t = min(x, y);
ret = (2ll*t*t%mod*(t+1)%mod*(t+1)%mod+4ll*t%mod*(t+1)%mod*(2*t+1)%mod*333333336%mod+(2ll*t+1)*(t+1)%mod)%mod;
if(x>y) ret += ((1ll*(x+y+1)+2+y)%mod*500000004%mod*(x-y)%mod+(2ll*x%mod*(x+1)%mod*(2*x+1)%mod-2ll*y%mod*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(y+1)%mod;
else ret += ((3ll*(x+y+1)+2-x)%mod*500000004%mod*(y-x)%mod+(-2ll*x%mod*(x+1)%mod*(2*x+1)%mod+2ll*y%mod*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(x+1)%mod;
}
return ret%mod;
}
int g(pair<pair<int, int>, pair<int, int> > p){
int x1,y1,x2,y2; tie(x1, y1) = p.first, tie(x2, y2) = p.second;
if(x1>x2 || y1>y2) return 0;
int ret;
if(x1>=0 && y1>=0) ret = (1ll*f(x2, y2)-(x1?f(x1-1, y2):0)-(y1?f(x2, y1-1):0)+(x1&&y1?f(x1-1, y1-1):0))%mod;
else if(y1>=0) ret = (1ll*f(x1, y2)-(x2?f(x2+1, y2):0)-(y1?f(x1, y1-1):0)+(x2&&y1?f(x2+1, y1-1):0))%mod;
else if(x1>=0) ret = (1ll*f(x2, y1)-(x1?f(x1-1, y1):0)-(y2?f(x2, y2+1):0)+(x1&&y2?f(x1-1, y2+1):0))%mod;
else ret = (1ll*f(x1, y1)-(x2?f(x2+1, y1):0)-(y2?f(x1, y2+1):0)+(x2&&y2?f(x2+1, y2+1):0))%mod;
return (ret+mod)%mod;
}
pair<pair<int, int>, pair<int, int> > h(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2){
return {{max(x1, X1), max(y1, Y1)}, {min(x2, X2), min(y2, Y2)}};
}
int main(){
int N,Q; scanf("%d%d",&N,&Q);
while(Q--){
int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int ans = (1ll*g(h(x1, y1, x2, y2, 0, 0, 1e9, 1e9))+g(h(x1, y1, x2, y2, -1e9, 0, -1, 1e9))+g(h(x1, y1, x2, y2, 0, -1e9, 1e9, -1))+g(h(x1, y1, x2, y2, -1e9, -1e9, -1, -1)))%mod;
printf("%d\n",ans);
continue;
}
return 0;
}