QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#559898 | #8669. 正方形计数 | lichenghan | 35 | 3280ms | 3864kb | C++14 | 1.1kb | 2024-09-12 10:20:26 | 2024-09-12 10:20:26 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2002;
const int V=2000;
int n;
int x[N],y[N];
int lef[N],rit[N]; // x=i y=[l,r]
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
for(int x=0;x<=V;x++) rit[x]=1e9;
x[n+1]=x[1]; y[n+1]=y[1];
for(int i=1;i<=n;i++){
ll a=y[i+1]-y[i],b=x[i]-x[i+1],c=x[i]*a+y[i]*b;
// ax+by>=c
for(int x=0;x<=V;x++){
// by>=c-ax
if(b==0){
if(c-a*x>0){
lef[x]=1e9; rit[x]=-1e9;
}
}else if(b>0){
lef[x]=max((ll)lef[x],(c-a*x+b-1)/b);
}else{
rit[x]=min((ll)rit[x],(c-a*x)/b);
}
}
}
for(int x=0;x<=V;x++){
if(lef[x]>rit[x]) lef[x]=1e9,rit[x]=-1e9;
// printf(" x=%d L=%d R=%d\n",x,lef[x],rit[x]);
}
int ans=0;
for(int a=0;a<=V;a++){
for(int b=1;a+b<=V;b++){
// printf("a=%d b=%d:\n",a,b);
for(int x=0;a+b+x<=V;x++){
int L=max({lef[x]-a,lef[x+a]-a-b,lef[x+b],lef[x+a+b]-b});
int R=min({rit[x]-a,rit[x+a]-a-b,rit[x+b],rit[x+a+b]-b});
if(L<=R) {
// printf(" x=%d L=%d R=%d\n",x,L,R);
ans+=R-L+1;
}
}
}
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3280ms
memory: 3856kb
input:
4 131 603 131 1828 1919 1828 1919 603
output:
405657336
result:
wrong answer 1st numbers differ - expected: '361182910200', found: '405657336'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 3187ms
memory: 3784kb
input:
3 131 603 131 1828 1919 603
output:
-685200259
result:
wrong answer 1st numbers differ - expected: '63739309181', found: '-685200259'
Subtask #3:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 3143ms
memory: 3824kb
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: 3151ms
memory: 3824kb
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: 3150ms
memory: 3832kb
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: 3153ms
memory: 3864kb
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: 3158ms
memory: 3664kb
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: 3149ms
memory: 3856kb
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: 3143ms
memory: 3848kb
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: 3143ms
memory: 3692kb
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: 3153ms
memory: 3752kb
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: 3144ms
memory: 3584kb
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: 3170ms
memory: 3612kb
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: 0
Wrong Answer
Dependency #4:
100%
Accepted
Test #22:
score: 0
Wrong Answer
time: 3162ms
memory: 3660kb
input:
5 257 800 766 800 800 353 667 0 42 0
output:
1701500430
result:
wrong answer 1st numbers differ - expected: '18881369614', found: '1701500430'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%