QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557703#8669. 正方形计数zero-range50 2772ms1680kbC++201.3kb2024-09-11 11:03:142024-09-11 11:03:14

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 11:03:14]
  • 评测
  • 测评结果:50
  • 用时:2772ms
  • 内存:1680kb
  • [2024-09-11 11:03:14]
  • 提交

answer

#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define M 2005
using namespace std;
int n,X[M],Y[M],lx=2000,rx=0,ly=2000,ry=0;
int Lx[M],Rx[M],Ly[M],Ry[M];
long long ans;
int S(int x1,int y1,int x2,int y2,int x3,int y3){
	x2-=x1,x3-=x1,y2-=y1,y3-=y1;
	return abs(x2*y3-x3*y2);
}
int cal(int x,int y){
	int sm=0;
	for(int i=0;i<n;++i) sm+=S(x,y,X[i],Y[i],X[i+1],Y[i+1]);
	return sm;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)	
		scanf("%d%d",X+i,Y+i),
		lx=min(lx,X[i]),ly=min(ly,Y[i]),
		rx=max(rx,X[i]),ry=max(ry,Y[i]);
	X[0]=X[n],Y[0]=Y[n];
	int R=cal(X[0],Y[0]);
	for(int y=ly;y<=ry;++y) Lx[y]=rx+1,Rx[y]=lx-1;
	for(int x=lx;x<=rx;++x){
		Ly[x]=ry+1,Ry[x]=ly-1;
		for(int y=ly;y<=ry;++y) if(cal(x,y)==R){Ly[x]=y;break;}
		int l=Ly[x],r=ry,mid;
		while(l<=r){
			mid=l+r>>1;
			if(cal(x,mid)==R) l=mid+1,Ry[x]=mid;
			else r=mid-1;
		}
		for(int y=Ly[x];y<=Ry[x];++y)
			Lx[y]=min(Lx[y],x),
			Rx[y]=max(Rx[y],x);
	}
	for(int x=lx;x<=rx;++x) for(int y=ly;y<=ry;++y){
		for(int k=1;x+k<=rx&&y+k<=ry;++k){
			int l=max({1,Ly[x]-y,Lx[y+k]-x,y+k-Ry[x+k],x+k-Rx[y]});
			int r=min({k,Ry[x]-y,Rx[y+k]-x,y+k-Ly[x+k],x+k-Lx[y]});
			if(l<=r) ans+=r-l+1;
		}
	}
	printf("%lld",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 10
Accepted
time: 2772ms
memory: 1636kb

input:

4
131 603
131 1828
1919 1828
1919 603

output:

361182910200

result:

ok 1 number(s): "361182910200"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1632kb

input:

4
239 211
239 962
261 962
261 211

output:

1498772

result:

ok 1 number(s): "1498772"

Test #3:

score: 0
Time Limit Exceeded

input:

4
0 0
0 2000
2000 2000
2000 0

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #6:

score: 25
Accepted
time: 2567ms
memory: 1512kb

input:

3
131 603
131 1828
1919 603

output:

63739309181

result:

ok 1 number(s): "63739309181"

Test #7:

score: 25
Accepted
time: 0ms
memory: 1664kb

input:

3
239 211
239 962
261 211

output:

353073

result:

ok 1 number(s): "353073"

Test #8:

score: 0
Time Limit Exceeded

input:

3
0 0
0 2000
2000 0

output:


result:


Subtask #3:

score: 15
Accepted

Test #11:

score: 15
Accepted
time: 0ms
memory: 1608kb

input:

8
0 13
4 15
15 15
15 6
13 1
12 0
5 0
0 6

output:

4047

result:

ok 1 number(s): "4047"

Test #12:

score: 15
Accepted
time: 0ms
memory: 1612kb

input:

8
0 4
1 15
2 15
15 14
15 4
14 0
1 0
0 2

output:

4200

result:

ok 1 number(s): "4200"

Test #13:

score: 15
Accepted
time: 0ms
memory: 1624kb

input:

5
7 15
15 13
15 0
3 0
0 15

output:

3635

result:

ok 1 number(s): "3635"

Test #14:

score: 15
Accepted
time: 0ms
memory: 1664kb

input:

8
0 12
2 14
7 15
13 15
15 10
15 1
8 0
0 0

output:

4511

result:

ok 1 number(s): "4511"

Test #15:

score: 15
Accepted
time: 0ms
memory: 1644kb

input:

6
0 11
3 15
7 15
15 12
10 0
0 0

output:

3006

result:

ok 1 number(s): "3006"

Test #16:

score: 15
Accepted
time: 0ms
memory: 1672kb

input:

5
0 0
0 2
1 2
2 1
2 0

output:

4

result:

ok 1 number(s): "4"

Subtask #4:

score: 20
Accepted

Dependency #3:

100%
Accepted

Test #17:

score: 20
Accepted
time: 25ms
memory: 1636kb

input:

8
49 299
144 300
300 260
250 15
115 0
30 0
23 19
0 85

output:

443602646

result:

ok 1 number(s): "443602646"

Test #18:

score: 20
Accepted
time: 20ms
memory: 1648kb

input:

8
0 133
103 300
130 300
257 294
297 227
300 150
277 40
161 4

output:

351466521

result:

ok 1 number(s): "351466521"

Test #19:

score: 20
Accepted
time: 24ms
memory: 1612kb

input:

8
76 286
114 300
300 300
300 205
291 0
47 0
4 57
2 235

output:

605026927

result:

ok 1 number(s): "605026927"

Test #20:

score: 20
Accepted
time: 21ms
memory: 1516kb

input:

8
0 102
40 274
282 300
300 234
267 0
34 0
6 57
0 86

output:

497330741

result:

ok 1 number(s): "497330741"

Test #21:

score: 20
Accepted
time: 25ms
memory: 1680kb

input:

7
0 288
156 300
212 300
265 176
300 86
278 0
0 36

output:

446722651

result:

ok 1 number(s): "446722651"

Subtask #5:

score: 15
Accepted

Dependency #4:

100%
Accepted

Test #22:

score: 15
Accepted
time: 415ms
memory: 1648kb

input:

5
257 800
766 800
800 353
667 0
42 0

output:

18881369614

result:

ok 1 number(s): "18881369614"

Test #23:

score: 15
Accepted
time: 353ms
memory: 1648kb

input:

8
691 800
737 795
800 651
372 98
136 266
118 318
24 629
12 753

output:

8760058886

result:

ok 1 number(s): "8760058886"

Test #24:

score: 15
Accepted
time: 379ms
memory: 1672kb

input:

8
718 800
740 800
800 726
800 670
711 367
595 150
86 0
57 136

output:

3064355626

result:

ok 1 number(s): "3064355626"

Test #25:

score: 15
Accepted
time: 451ms
memory: 1672kb

input:

8
0 347
16 449
364 798
674 800
750 800
797 14
195 0
0 70

output:

23587042437

result:

ok 1 number(s): "23587042437"

Test #26:

score: 15
Accepted
time: 457ms
memory: 1648kb

input:

8
322 800
596 800
686 777
800 280
764 69
396 0
46 179
0 660

output:

23185884331

result:

ok 1 number(s): "23185884331"

Subtask #6:

score: 0
Skipped

Dependency #1:

0%