oj.uz

Submission #262792

# Submission time Handle Problem Language Result Execution time Memory
262792 2020-08-13T09:04:49 Z TadijaSebez Spiral (BOI16_spiral) C++11
100 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
void ck(int&x){if(x<0)x+=mod;}
int add(int x,int y){ck(x);ck(y);x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){ck(x);ck(y);x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
void ckadd(int&x,int y){x=add(x,y);}
int GetCell(int x,int y){
	int mx=max(abs(x),abs(y));
	int ans=mul(sub(mul(2,mx),1),sub(mul(2,mx),1));
	if(y==mx)ckadd(ans,add(sub(mx,x),mul(mx,2)));
	else if(x==-mx)ckadd(ans,add(sub(mx,y),mul(mx,4)));
	else if(y==-mx)ckadd(ans,add(x,mul(mx,7)));
	else if(x==mx)ckadd(ans,add(y,mx));
	return ans;
}
int sum0(int n){return n+1;}
int sum1(int n){return mul(mul(n,n+1),(mod+1)/2);}
int sum2(int n){return mul(mul(n,n+1),mul((2*n+1)%mod,mul((mod+1)/2,(mod+1)/3)));}
int sum3(int n){return mul(sum1(n),sum1(n));}
int GetSQ(int now,int dif,int n){
	int T1=sum1(n);
	int T2=mul(2,sum2(n));
	int T3=add(add(mul(now,sum0(n)),mul(dif,sum1(n)))
		  ,mul(4,sub(sum2(n),sum1(n))));
	int T4=mul(2,add(add(mul(now,sum1(n)),mul(dif,sum2(n)))
		  ,mul(4,sub(sum3(n),sum2(n)))));
	return add(add(T1,T2),add(T3,T4));
}
int GetST(int now,int nxt,int len,int n){
	int dif=nxt-now;
	int T1=add(mul(now,sum0(n-1)),mul(dif,sum1(n-1)));
	int T2=mul(4,sub(sum2(n-1),sum1(n-1)));
	int T3=mul(n,sum1(len-1));
	return add(mul(len,add(T1,T2)),T3);
}
int Ari(int now,int dif,int n){
	return add(mul(now,sum0(n)),add(mul(dif,sum1(n)),mul(4,sub(sum2(n),sum1(n)))));
}
int Get(int x,int y){
	int n=min(abs(x),abs(y)),ans;
	if(x>=0&&y>=0){
		ans=GetSQ(1,1,n);
		if(abs(x)>abs(y))ckadd(ans,GetST(GetCell(y+1,0),GetCell(y+2,0),n+1,abs(x)-abs(y)));
		if(abs(x)<abs(y))ckadd(ans,GetST(GetCell(x,x+1),GetCell(x,x+2),n+1,abs(y)-abs(x)));
	}else if(x>=0&&y<0){
		ans=add((n>0?GetSQ(2,7,n-1):0),Ari(1,7,n));
		ckadd(ans,add(mul(n,GetCell(0,-n)),sum1(n)));
		if(abs(x)>abs(y))ckadd(ans,GetST(GetCell(-y+1,y),GetCell(-y+2,y),n+1,abs(x)-abs(y)));
		if(abs(x)<abs(y))ckadd(ans,GetST(GetCell(0,-x-1),GetCell(0,-x-2),n+1,abs(y)-abs(x)));
	}else if(x<0&&y>=0){
		ans=GetSQ(1,3,n);
		if(abs(x)>abs(y))ckadd(ans,GetST(GetCell(-y-1,y),GetCell(-y-2,y),n+1,abs(x)-abs(y)));
		if(abs(x)<abs(y))ckadd(ans,GetST(GetCell(0,-x+1),GetCell(0,-x+2),n+1,abs(y)-abs(x)));
	}else if(x<0&&y<0){
		ans=GetSQ(1,5,n);
		if(abs(x)>abs(y))ckadd(ans,GetST(GetCell(y-1,0),GetCell(y-2,0),n+1,abs(x)-abs(y)));
		if(abs(x)<abs(y))ckadd(ans,GetST(GetCell(x,x-1),GetCell(x,x-2),n+1,abs(y)-abs(x)));
	}
	return ans;
}
int Get(int x1,int y1,int x2,int y2){
	if(x1>x2||y1>y2)return 0;
	if(x1>=0&&y1>=0)return sub(add(Get(x2,y2),x1!=0&&y1!=0?Get(x1-1,y1-1):0),add(x1!=0?Get(x1-1,y2):0,y1!=0?Get(x2,y1-1):0));
	if(x1<0&&y1>=0)return sub(add(Get(x1,y2),x2!=0&&y1!=0?Get(x2+1,y1-1):0),add(x2!=0?Get(x2+1,y2):0,y1!=0?Get(x1,y1-1):0));
	if(x1>=0&&y1<0)return sub(add(Get(x2,y1),x1!=0&&y2!=0?Get(x1-1,y2+1):0),add(x1!=0?Get(x1-1,y1):0,y2!=0?Get(x2,y2+1):0));
	if(x1<0&&y1<0)return sub(add(Get(x1,y1),x2!=0&&y2!=0?Get(x2+1,y2+1):0),add(x2!=0?Get(x2+1,y1):0,y2!=0?Get(x1,y2+1):0));
}
int main(){
	int n,q;
	scanf("%i %i",&n,&q);
	while(q--){
		int x1,y1,x2,y2;
		scanf("%i %i %i %i",&x1,&y1,&x2,&y2);
		int ans=add(add(Get(max(0,x1),max(0,y1),x2,y2),Get(x1,max(0,y1),min(-1,x2),y2)),add(Get(max(0,x1),y1,x2,min(-1,y2)),Get(x1,y1,min(-1,x2),min(-1,y2))));
		printf("%i\n",ans);
	}
	return 0;
}

Compilation message

spiral.cpp: In function 'int Get(int, int, int, int)':
spiral.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^
spiral.cpp: In function 'int main()':
spiral.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |  scanf("%i %i",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~~
spiral.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |   scanf("%i %i %i %i",&x1,&y1,&x2,&y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
spiral.cpp: In function 'int Get(int, int)':
spiral.cpp:62:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  return ans;
      |         ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct