This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 2147483647
int n,x1,y3,x2,y2,dp1[2510][2510],dp2[2510][2510],cnt[2510][2510],cnt2[2510][2510],cnt4[2510][2510];
long long dap;
int arr[2510][2510];
struct data{
int x,y;
}a[250010];
struct data2{
int x,y;
}d1[2510][2510];
struct data3{
int x,y;
}d2[2510][2510];
int main()
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&a[i].x,&a[i].y); arr[a[i].x][a[i].y]=1;
}
for(i=0;i<=2501;i++){
for(j=0;j<=2501;j++){
d1[i][j].x=d1[i][j].y=M;
d2[i][j].x=d2[i][j].y=-M;
}
}
for(i=1;i<=2500;i++){
for(j=1;j<=2500;j++){
d1[i][j].x=min(d1[i][j].x,min(d1[i][j-1].x,d1[i-1][j].x));
if(arr[i][j]) d1[i][j].x=min(d1[i][j].x,i);
d1[i][j].y=min(d1[i][j].y,min(d1[i][j-1].y,d1[i-1][j].y));
if(arr[i][j]) d1[i][j].y=min(d1[i][j].y,j);
cnt2[i][j]=cnt2[i-1][j]+cnt2[i][j-1]-cnt2[i-1][j-1]+arr[i][j];
}
}
for(i=2500;i>=1;i--){
for(j=2500;j>=1;j--){
d2[i][j].x=max(d2[i][j].x,max(d2[i][j+1].x,d2[i+1][j].x));
if(arr[i][j]) d2[i][j].x=max(d2[i][j].x,i);
d2[i][j].y=max(d2[i][j].y,max(d2[i][j+1].y,d2[i+1][j].y));
if(arr[i][j]) d2[i][j].y=max(d2[i][j].y,j);
cnt4[i][j]=cnt4[i+1][j]+cnt4[i][j+1]-cnt4[i+1][j+1]+arr[i][j];
}
}
for(i=1;i<=2500;i++){
for(j=2500;j>=1;j--){
cnt[i][j]=cnt[i-1][j]+cnt[i][j+1]-cnt[i-1][j+1]+arr[i][j];
x1=d1[i][j-1].x; y3=d2[i+1][j].y;
dp1[i][j]=dp1[x1][y3]+cnt[i][j];
}
}
for(i=2500;i>=1;i--)
{
for(j=1;j<=2500;j++)
{
cnt[i][j]=cnt[i+1][j]+cnt[i][j-1]-cnt[i+1][j-1]+arr[i][j];
x2=d2[i][j+1].x; y2=d1[i-1][j].y;
dp2[i][j]=dp2[x2][y2]+cnt[i][j];
}
}
for(i=1;i<=n;i++){
dap=0;
x1=d1[a[i].x-1][a[i].y-1].x; y2=d1[a[i].x-1][a[i].y-1].y;
x2=d2[a[i].x+1][a[i].y+1].x; y3=d2[a[i].x+1][a[i].y+1].y;
if(x1==2147483647) x1=a[i].x, y2=a[i].y;
if(x2==-2147483647) x2=a[i].x, y3=a[i].y;
dap+=n-1;
dap+=n-cnt2[a[i].x-1][a[i].y-1]-cnt4[a[i].x+1][a[i].y+1];
dap+=dp1[x1][y3]+dp2[x2][y2];
printf("%lld\n",dap-1);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |