Submission #98170

#	Time	Username	Problem	Language	Result	Execution time	Memory
98170		maruii	Spiral (BOI16_spiral)	C++14	100 / 100	3 ms	384 KiB

spiral

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
using rrint = int;
#define int long long
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)+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)+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)+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)+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 (stderr)

spiral.cpp: In function 'rrint main()':
spiral.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rrint N,Q; scanf("%d%d",&N,&Q);
             ~~~~~^~~~~~~~~~~~~~
spiral.cpp:53:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   rrint x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25