Code Submission Evaluation System Login

BOI 2016, day 1

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

Tasks | Scoreboard | Statistics


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
Task:Spiral
Sender:gskhirtladze
Submission time:2016-05-12 13:21:28
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED12
#2ACCEPTED15
#3ACCEPTED17
#4ACCEPTED31
#5ACCEPTED25

Test results

testverdicttime (s)group
#1ACCEPTED0.05 / 1.501details
#2ACCEPTED0.05 / 1.502details
#3ACCEPTED0.06 / 1.503details
#4ACCEPTED0.05 / 1.504details
#5ACCEPTED0.06 / 1.505details

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
788057008
633127082
507903329
53165899
558016315
...
view   save

user output
788057008
633127082
507903329
53165899
558016315
...
view   save

Test 2

Group: 2

Verdict: ACCEPTED

input
1000000000 100
181053719 1000000000 181053719...
view   save

correct output
818946492
750635163
193830026
660632411
46072376
...
view   save

user output
818946492
750635163
193830026
660632411
46072376
...
view   save

Test 3

Group: 3

Verdict: ACCEPTED

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

correct output
986592951
708386765
85336595
18263594
32233727
...
view   save

user output
986592951
708386765
85336595
18263594
32233727
...
view   save

Test 4

Group: 4

Verdict: ACCEPTED

input
1000000000 100
1 1 21134200 719983102
1 1 929463279 1000000000
1 1 68450838 1
1 1 84417340 297177199
...
view   save

correct output
695961158
957360176
137575768
522232140
58884045
...
view   save

user output
695961158
957360176
137575768
522232140
58884045
...
view   save

Test 5

Group: 5

Verdict: ACCEPTED

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

correct output
902627632
581519884
819269364
857298983
278402948
...
view   save

user output
902627632
581519884
819269364
857298983
278402948
...
view   save