| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 98172 |
2019-02-21T06:18:47 Z |
maruii |
Spiral (BOI16_spiral) |
C++14 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int f(int x, int y){
int ret;
if(x>=0 && y>=0){
int t = min(x, y);
ret = (2ll*t*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*(x+1)%mod*(2*x+1)%mod-2ll*y*(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*(x+1)%mod*(2*x+1)%mod+2ll*y*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(x+1)%mod;
}
else if(y>=0){
x = -x;
int t = min(x, y);
ret = (2ll*t*t%mod*(t+1)%mod*(t+1)%mod+2ll*t*(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*(x+1)%mod*(2*x+1)%mod-2ll*y*(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*(x+1)%mod*(2*x+1)%mod+2ll*y*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(x+1)%mod;
}
else if(x>=0){
y = -y;
int t = min(x, y);
ret = (2ll*t*t%mod*(t+1)%mod*(t+1)%mod+2ll*t*(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*(x+1)%mod*(2*x+1)%mod-2ll*y*(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*(x+1)%mod*(2*x+1)%mod+2ll*y*(y+1)%mod*(2*y+1)%mod+mod)%mod*333333336%mod)%mod*(x+1)%mod;
}
else{
x = -x, y = -y;
int t = min(x, y);
ret = (2ll*t*t%mod*(t+1)%mod*(t+1)%mod+4ll*t*(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*(x+1)%mod*(2*x+1)%mod-2ll*y*(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*(x+1)%mod*(2*x+1)%mod+2ll*y*(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)}};
}
rrint main(){
rrint N,Q; scanf("%d%d",&N,&Q);
while(Q--){
rrint x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
rrint 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;
}
Compilation message
spiral.cpp:48:1: error: 'rrint' does not name a type; did you mean 'rint'?
rrint main(){
^~~~~
rint
