QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#560496#8669. 正方形计数free_fall0 3526ms6592kbC++141.1kb2024-09-12 15:59:592024-09-12 15:59:59

Judging History

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

  • [2024-09-12 15:59:59]
  • 评测
  • 测评结果:0
  • 用时:3526ms
  • 内存:6592kb
  • [2024-09-12 15:59:59]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-f;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
const int N=1e5+5,inf=0x3f3f3f3f3f3f3f3f;
int n,x[N],y[N],f[N],g[N];
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		x[i]=read(),y[i]=read();
	}
	memset(f,-0x3f,sizeof f);
	memset(g,0x3f,sizeof g);
	x[n+1]=x[1],y[n+1]=y[1];
	for(int i=1;i<=n;i++){
		int a=x[i]-x[i+1],b=y[i+1]-y[i],c=x[i]*b+y[i]*a;
		for(int j=0;j<=2e3;j++){
			if(x[i]>x[i+1])f[j]=max(f[j],(c-b*j+a-1)/a);
			if(x[i]<x[i+1])g[j]=min(g[j],(c-b*j)/a);
			if(x[i]==x[i+1]&&c-b*j>0)f[j]=inf,g[j]=-inf;
		}
	}
	for(int i=0;i<=2e3;i++){
		if(f[i]>g[i])f[i]=inf,g[i]=-inf;
	}
	int ans=0;
	for(int i=0;i<=2e3;i++){
		printf("%lld\n",i);
		for(int j=1;i+j<=2e3;j++){
			for(int k=0;i+j+k<=2e3;k++){
				int L=max({f[k]-i,f[k+i]-i-j,f[k+j],f[k+i+j]-j});
				int R=min({g[k]-i,g[k+i]-i-j,g[k+j],g[k+i+j]-j});
				if(L>R)continue;
				ans+=R-L+1;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3526ms
memory: 5452kb

input:

4
131 603
131 1828
1919 1828
1919 603

output:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
10...

result:

wrong answer 1st numbers differ - expected: '361182910200', found: '0'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 3436ms
memory: 6592kb

input:

3
131 603
131 1828
1919 603

output:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
10...

result:

wrong answer 1st numbers differ - expected: '63739309181', found: '0'

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 3388ms
memory: 5388kb

input:

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

output:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
10...

result:

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

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%