| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 98164 |
2019-02-21T04:17:53 Z |
maruii |
Spiral (BOI16_spiral) |
C++14 |
|
4 ms |
512 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 += ((2ll*y+1)*(2*y+1)%mod+(2ll*x-1)*(2*x-1)%mod+2*y+x+1)%mod*500000004%mod*(y+1)%mod*(x-y)%mod;
else ret += (4ll*(x+1)*(x+1)%mod+(4ll*y-1)*y%mod+1-2*x)%mod*500000004%mod*(x+1)%mod*(y-x)%mod;
ret %= 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 += ((4ll*x+1)*x%mod+(4ll*y+5)*(y+1)%mod+2-y)%mod*500000004%mod*(y+1)%mod*(x-y)%mod;
else ret += (4ll*(x+1)*(x+1)%mod+(4ll*y-1)*y%mod+1)%mod*500000004%mod*(x+1)%mod*(y-x)%mod;
ret %= 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 += ((2ll*y+1)*(2*y+1)%mod+(2ll*x-1)*(2*x-1)%mod+x+1)%mod*500000004%mod*(y+1)%mod*(x-y)%mod;
else ret += ((2ll*x+3)*(2*x+3)%mod+(2ll*y+1)*(2*y+1)%mod-y-1)%mod*500000004%mod*(y-x)%mod*(x+1)%mod;
ret %= 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 += ((4ll*x+1)*x%mod+(4ll*y+5)*(y+1)%mod+2+y)%mod*500000004%mod*(y+1)%mod*(x-y)%mod;
else ret += ((2ll*x+3)*(2*x+3)%mod+(2ll*y+1)*(2*y+1)%mod-2*x-y-1)%mod*500000004%mod*(y-x)%mod*(x+1)%mod;
ret %= mod;
}
return ret;
}
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;
ret = (ret+mod)%mod;
return ret;
}
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;
}
Compilation message
spiral.cpp: In function 'int main()':
spiral.cpp:54:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N,Q; scanf("%d%d",&N,&Q);
~~~~~^~~~~~~~~~~~~~
spiral.cpp:56:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
