# BOI 2016, day 1

 Start: 2016-05-12 09:00:00 End: 2016-05-12 14:00:00

CSES - BOI 2016, day 1 - Results
History
2016-05-12 13:21:28100
2016-05-12 12:12:2531
2016-05-12 12:01:530

## Feedback

 group verdict score #1 ACCEPTED 12 #2 ACCEPTED 15 #3 ACCEPTED 17 #4 ACCEPTED 31 #5 ACCEPTED 25

## Test results

 test verdict time (s) group #1 ACCEPTED 0.05 / 1.50 1 details #2 ACCEPTED 0.05 / 1.50 2 details #3 ACCEPTED 0.06 / 1.50 3 details #4 ACCEPTED 0.05 / 1.50 4 details #5 ACCEPTED 0.06 / 1.50 5 details

## Code

```#include <bits/stdc++.h>

#define P 1000000007
using namespace std;

int get_cubes(int x)
{
int D=(1LL*x*(x+1)/2)%P;
D=(1LL*D*D)%P;
return D;
}

int get_square(int x)
{
int A=x;
int B=(x+1);
int C=(2*x+1);
if (A%2 == 0) A/=2; else
if (B%2 == 0) B/=2; else C/=2;
if (A%3 == 0) A/=3; else
if (B%3 == 0) B/=3; else C/=3;
int D=(1LL*((1LL*A*B)%P)*C)%P;
return D;
}

int get_sum(int x)
{
int D=(1LL*x*(x+1)/2)%P;
return D;
}

int get_0_0_X_X(int x)
{
int D=(1LL*(8LL*get_cubes(x))%P-(20LL*get_square(x))%P+(14LL*get_sum(x))%P-
(4LL*get_square(x))%P+(10LL*get_sum(x))%P-(7LL*x)%P)%P;
D=(D+P)%P;
return D;
}

int get_0_0_x_X(int x)
{
int D=(1LL*(8LL*get_cubes(x))%P-(16LL*get_square(x))%P+(10LL*get_sum(x))%P-
(4LL*get_square(x))%P+(8LL*get_sum(x))%P-(5LL*x)%P)%P;
D=(D+P)%P;
return D;
}

int get_0_0_x_x(int x)
{
int D=(1LL*(8LL*get_cubes(x))%P-(12LL*get_square(x))%P+(6LL*get_sum(x))%P-
(4LL*get_square(x))%P+(6LL*get_sum(x))%P-(3LL*x)%P)%P;
D=(D+P)%P;
return D;
}

int get_0_0_X_x(int x)
{
int D=(1LL*(8LL*get_cubes(x))%P-(8LL*get_square(x))%P+(4LL*get_sum(x))%P-
(4LL*get_square(x))%P+(4LL*get_sum(x))%P-(2LL*x)%P)%P;
D=(D+P)%P;
return D;
}

int get_0_0_X_Y(int x,int y)
{
x++; y++;
int ans=get_0_0_X_X(min(x,y));
if (x == y) return ans;
if (x > y)
{
int D=ans;
D=(1LL*D+(((4LL*y)%P)*get_square(x))%P-(((11LL*y)%P)*get_sum(x))%P)%P;
D=(1LL*D+(((8LL*x)%P)*y)%P+(1LL*x*((1LL*y*(y-1)/2)%P))%P)%P;
D=(1LL*D-(((4LL*y)%P)*get_square(y))%P+(((11LL*y)%P)*get_sum(y))%P)%P;
D=(1LL*D-(((8LL*y)%P)*y)%P-(1LL*y*((1LL*y*(y-1)/2)%P))%P)%P;
return (D+P)%P;
} else
{
swap(x,y);
int D=ans;
D=(1LL*D+(((4LL*y)%P)*get_square(x))%P-(((9LL*y)%P)*get_sum(x))%P)%P;
D=(1LL*D+(((6LL*x)%P)*y)%P-(1LL*x*((1LL*y*(y-1)/2)%P))%P)%P;
D=(1LL*D-(((4LL*y)%P)*get_square(y))%P+(((9LL*y)%P)*get_sum(y))%P)%P;
D=(1LL*D-(((6LL*y)%P)*y)%P+(1LL*y*((1LL*y*(y-1)/2)%P))%P)%P;
return (D+P)%P;
}

}

int get_0_0_x_Y(int x,int y)
{
x*=-1;
x++; y++;
int ans=get_0_0_x_X(min(x,y));
if (x == y) return ans;
if (x > y)
{
int D=ans;
D=(1LL*D+(((4LL*y)%P)*get_square(x))%P-(((7LL*y)%P)*get_sum(x))%P)%P;
D=(1LL*D+(((4LL*x)%P)*y)%P-(1LL*x*((1LL*y*(y-1)/2)%P))%P)%P;
D=(1LL*D-(((4LL*y)%P)*get_square(y))%P+(((7LL*y)%P)*get_sum(y))%P)%P;
D=(1LL*D-(((4LL*y)%P)*y)%P+(1LL*y*((1LL*y*(y-1)/2)%P))%P)%P;
return (D+P)%P;
} else
{
swap(x,y);
int D=ans;
D=(1LL*D+(((4LL*y)%P)*get_square(x))%P-(((9LL*y)%P)*get_sum(x))%P)%P;
D=(1LL*D+(((6LL*x)%P)*y)%P+(1LL*x*((1LL*y*(y-1)/2)%P))%P)%P;
D=(1LL*D-(((4LL*y)%P)*get_square(y))%P+(((9LL*y)%P)*get_sum(y))%P)%P;
D=(1LL*D-(((6LL*y)%P)*y)%P-(1LL*y*((1LL*y*(y-1)/2)%P))%P)%P;
return (D+P)%P;
}

}

int get_0_0_x_y(int x,int y)
{
x*=-1; y*=-1;
x++; y++;
int ans=get_0_0_x_x(min(x,y));
if (x == y) return ans;
if (x > y)
{
int D=ans;
D=(1LL*D+(((4LL*y)%P)*get_square(x))%P-(((7LL*y)%P)*get_sum(x))%P)%P;
D=(1LL*D+(((4LL*x)%P)*y)%P+(1LL*x*((1LL*y*(y-1)/2)%P))%P)%P;
D=(1LL*D-(((4LL*y)%P)*get_square(y))%P+(((7LL*y)%P)*get_sum(y))%P)%P;
D=(1LL*D-(((4LL*y)%P)*y)%P-(1LL*y*((1LL*y*(y-1)/2)%P))%P)%P;
return (D+P)%P;
} else
{
swap(x,y);
int D=ans;
D=(1LL*D+(((4LL*y)%P)*get_square(x))%P-(((5LL*y)%P)*get_sum(x))%P)%P;
D=(1LL*D+(((2LL*x)%P)*y)%P-(1LL*x*((1LL*y*(y-1)/2)%P))%P)%P;
D=(1LL*D-(((4LL*y)%P)*get_square(y))%P+(((5LL*y)%P)*get_sum(y))%P)%P;
D=(1LL*D-(((2LL*y)%P)*y)%P+(1LL*y*((1LL*y*(y-1)/2)%P))%P)%P;
return (D+P)%P;
}

}

int get_0_0_X_y(int x,int y)
{
y*=-1; y++;
int ans=get_0_0_X_x(min(x,y));
if (x == y) return ans;
if (x > y)
{
int D=ans;
D=(1LL*D+(((4LL*y)%P)*get_square(x))%P-(((3LL*y)%P)*get_sum(x))%P)%P;
D=(1LL*D+(((1LL*x)%P)*y)%P-(1LL*x*((1LL*y*(y-1)/2)%P))%P)%P;
D=(1LL*D-(((4LL*y)%P)*get_square(y))%P+(((3LL*y)%P)*get_sum(y))%P)%P;
D=(1LL*D-(((1LL*y)%P)*y)%P+(1LL*y*((1LL*y*(y-1)/2)%P))%P)%P;
return (D+P)%P;
} else
{
swap(x,y);
int D=ans;
D=(1LL*D+(((4LL*y)%P)*get_square(x))%P-(((5LL*y)%P)*get_sum(x))%P)%P;
D=(1LL*D+(((3LL*x)%P)*y)%P+(1LL*x*((1LL*y*(y-1)/2)%P))%P)%P;
D=(1LL*D-(((4LL*y)%P)*get_square(y))%P+(((5LL*y)%P)*get_sum(y))%P)%P;
D=(1LL*D-(((3LL*y)%P)*y)%P-(1LL*y*((1LL*y*(y-1)/2)%P))%P)%P;
return (D+P)%P;
}

}

int get_X_Y(int xa,int ya,int xb,int yb)
{
if (xa > xb || ya > yb) return 0;
int D=get_0_0_X_Y(xb,yb);
if (xa >= 1) D=(D-get_0_0_X_Y(xa-1,yb))%P;
if (ya >= 1) D=(D-get_0_0_X_Y(xb,ya-1))%P;
if (xa >= 1 && ya >= 1) D=(D+get_0_0_X_Y(xa-1,ya-1))%P;
D=(D+P)%P;
return D;
}

int get_x_Y(int xa,int ya,int xb,int yb)
{
if (xa > xb || ya > yb) return 0;
swap(xa,xb);
int D=get_0_0_x_Y(xb,yb);
if (xa <= -1) D=(D-get_0_0_x_Y(xa+1,yb))%P;
if (ya >= 1) D=(D-get_0_0_x_Y(xb,ya-1))%P;
if (xa <= -1 && ya >= 1) D=(D+get_0_0_x_Y(xa+1,ya-1))%P;
D=(D+P)%P;
return D;
}

int get_x_y(int xa,int ya,int xb,int yb)
{
if (xa > xb || ya > yb) return 0;
swap(xa,xb);
swap(ya,yb);
int D=get_0_0_x_y(xb,yb);
if (xa <= -1) D=(D-get_0_0_x_y(xa+1,yb))%P;
if (ya <= -1) D=(D-get_0_0_x_y(xb,ya+1))%P;
if (xa <= -1 && ya <= -1) D=(D+get_0_0_x_y(xa+1,ya+1))%P;
D=(D+P)%P;
return D;
}

int get_X_y(int xa,int ya,int xb,int yb)
{
if (xa > xb || ya > yb) return 0;
swap(ya,yb);
int D=get_0_0_X_y(xb,yb);
if (xa >= 2) D=(D-get_0_0_X_y(xa-1,yb))%P;
if (ya <= -1) D=(D-get_0_0_X_y(xb,ya+1))%P;
if (xa >= 2 && ya <= -1) D=(D+get_0_0_X_y(xa-1,ya+1))%P;
D=(D+P)%P;
return D;
}

int n,q,xa,ya,xb,yb,A,B,C,D;

int main()
{
cin>>n>>q;
while (q--)
{
cin>>xa>>ya>>xb>>yb;
A=get_X_Y(max(xa,1),max(ya,1),xb,yb);
B=get_x_Y(xa,max(1,ya),min(xb,0),yb);
C=get_x_y(xa,ya,min(0,xb),min(0,yb));
D=get_X_y(max(xa,1),ya,xb,min(yb,0));
cout<<(1LL*A+1LL*B+1LL*C+1LL*D+4LL*P)%P<<endl;
}
}
```

## Test details

### Test 1

Group: 1

Verdict: ACCEPTED

input
`1000 100-709 0 1000 123-621 -1000 -102 -435-602 -560 276 -356-945 -590 0 -468...`
view   save

correct output
`78805700863312708250790332953165899558016315...`
view   save

user output
`78805700863312708250790332953165899558016315...`
view   save

### Test 2

Group: 2

Verdict: ACCEPTED

input
`1000000000 100181053719 1000000000 181053719...`
view   save

correct output
`81894649275063516319383002666063241146072376...`
view   save

user output
`81894649275063516319383002666063241146072376...`
view   save

### Test 3

Group: 3

Verdict: ACCEPTED

input
`100000 100-88233 -87279 -49871 52277-86645 -7997 48948 30702-79916 -36210 -21257 -168210 57331 93163 100000...`
view   save

correct output
`986592951708386765853365951826359432233727...`
view   save

user output
`986592951708386765853365951826359432233727...`
view   save

### Test 4

Group: 4

Verdict: ACCEPTED

input
`1000000000 1001 1 21134200 7199831021 1 929463279 10000000001 1 68450838 11 1 84417340 297177199...`
view   save

correct output
`69596115895736017613757576852223214058884045...`
view   save

user output
`69596115895736017613757576852223214058884045...`
view   save

### Test 5

Group: 5

Verdict: ACCEPTED

input
`1000000000 100-857489445 -1000000000 -432836...`
view   save

correct output
`902627632581519884819269364857298983278402948...`
view   save

user output
`902627632581519884819269364857298983278402948...`
view   save