oj.uz

Submission #98167

# Submission time Handle Problem Language Result Execution time Memory
98167 2019-02-21T06:08:12 Z maruii Spiral (BOI16_spiral) C++14
75 / 100
 3 ms 404 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 += (((mod-3ll)*(x+y+1)+2+y)%mod*500000004%mod*(x-y)+(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)+(-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)+(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)+(-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)+(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)+(-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)+(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)+(-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;
	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+1, 1e9+1))+g(h(x1, y1, x2, y2, -1e9-1, 0, -1, 1e9+1))+g(h(x1, y1, x2, y2, 0, -1e9-1, 1e9+1, -1))+g(h(x1, y1, x2, y2, -1e9-1, -1e9-1, -1, -1)))%mod;
		printf("%d\n",ans);
		continue;
	}
	return 0;
}

Compilation message

spiral.cpp: In function 'int main()':
spiral.cpp:50: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:52: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);
                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
31.0 / 31.0

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

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 3 ms 404 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Incorrect 3 ms 304 KB Output isn't correct