QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557699#8669. 正方形计数zero-range25 2754ms1672kbC++201.3kb2024-09-11 11:02:222024-09-11 11:02:23

Judging History

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

  • [2024-09-11 11:02:23]
  • 评测
  • 测评结果:25
  • 用时:2754ms
  • 内存:1672kb
  • [2024-09-11 11:02:22]
  • 提交

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;
			else break;
		}
	}
	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: 2754ms
memory: 1672kb

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: 1636kb

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: 25
Accepted

Test #6:

score: 25
Accepted
time: 943ms
memory: 1672kb

input:

3
131 603
131 1828
1919 603

output:

63739309181

result:

ok 1 number(s): "63739309181"

Test #7:

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

input:

3
239 211
239 962
261 211

output:

353073

result:

ok 1 number(s): "353073"

Test #8:

score: 25
Accepted
time: 2380ms
memory: 1648kb

input:

3
0 0
0 2000
2000 0

output:

222889277611

result:

ok 1 number(s): "222889277611"

Test #9:

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

input:

3
36 771
36 786
672 771

output:

98847

result:

ok 1 number(s): "98847"

Test #10:

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

input:

3
0 0
0 100
100 0

output:

1473186

result:

ok 1 number(s): "1473186"

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 1612kb

input:

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

output:

3326

result:

wrong answer 1st numbers differ - expected: '4047', found: '3326'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%