#include <bits/stdc++.h>
using namespace std;
int d;
int n,m,t;
struct A{
int v,l,r;
}seg[20000000];
int idx;
int tree[4003];
short s1[4003][4003];
short s2[4003][4003];
short a[4003][4003];
int b[4003][4003];
int c[4003][4003];
int mx;
long long ans;
int f(int lev,int l,int r,int k){
if(r==k)return seg[lev].v;
int mid=(l+r)/2;
if(k<=mid)return f(seg[lev].l,l,mid,k);
return seg[seg[lev].l].v+f(seg[lev].r,mid+1,r,k);
}
void make_first(int lev,int l,int r,int k){
mx=max(mx,lev);
if(l<=k && k<=r)seg[lev].v++;
if(l==r)return;
int mid=(l+r)/2;
seg[lev].l=++idx;
make_first(idx,l,mid,k);
seg[lev].r=++idx;
make_first(idx,mid+1,r,k);
}
void make_tree(int lev,int blev,int l,int r,int k){
mx=max(lev,mx);
seg[lev].v=seg[blev].v+1;
if(l==r)return;
int mid=(l+r)/2;
if(k<=mid){
seg[lev].r=seg[blev].r;
seg[lev].l=++idx;
make_tree(idx,seg[blev].l,l,mid,k);
}
else{
seg[lev].l=seg[blev].l;
seg[lev].r=++idx;
make_tree(idx,seg[blev].r,mid+1,r,k);
}
}
int main(){
int i,j;
scanf("%d %d %d %d",&n,&m,&d,&t);
for(i=1 ; i<=t ; i++){
int x,y;
scanf("%d %d",&x,&y);
a[x][y]=1;
}
for(i=1 ; i<=n ; i++)for(j=1 ; j<=m ; j++)s1[i][j]=s1[i][j-1]+a[i][j],s2[i][j]=s2[i-1][j]+a[i][j];
for(i=1 ; i<=n ; i++){
for(j=1 ; j<=m ; j++){
int lef=1;
int rig=min(n-i+1,m-j+1);
while(rig>=lef){
int mid=(lef+rig)/2;
if(s1[i][j+mid-1]-s1[i][j-1]==0 && s2[i+mid-1][j]-s2[i-1][j]==0){
b[i][j]=i+mid-1;
lef=mid+1;
}
else
rig=mid-1;
}
lef=1;
rig=min(i,j);
c[i][j]=rig;
while(rig>=lef){
int mid=(lef+rig)/2;
if(s1[i][j]-s1[i][j-mid]==0 && s2[i][j]-s2[i-mid][j]==0){
c[i][j]=i-mid+1;
lef=mid+1;
}
else
rig=mid-1;
}
}
}
for(int p=1 ; p<=n+m-1 ; p++){
idx=0;
if(p<=m){
i=1;
j=i+m-p;
tree[i]=++idx;
make_first(tree[i],1,min(n,p),c[i][j]);
i++;
for( ; i<=min(n,p) ; i++){
j=i+m-p;
tree[i]=++idx;
make_tree(tree[i],tree[i-1],1,min(n,p),c[i][j]);
}
for(i=1 ; i<=min(n,p) ; i++){
j=i+m-p;
if(b[i][j]>=i+d-1){
ans+=f(tree[b[i][j]],1,min(n,p),i)-
f(tree[i+d-2],1,min(n,p),i);
// printf("%d %d %d\n",i,j,ans);
}
}
}
else{
i=p-m+1;
j=i+m-p;
tree[i]=++idx;
make_first(tree[i],i,min(n,p),c[i][j]);
i++;
for( ; i<=min(n,p) ; i++){
j=i+m-p;
tree[i]=++idx;
make_tree(tree[i],tree[i-1],p-m+1,min(n,p),c[i][j]);
}
for(i=p-m+1 ; i<=min(n,p) ; i++){
j=i+m-p;
if(b[i][j]>=i+d-1){
ans+=f(tree[b[i][j]],p-m+1,min(n,p),i)-
f(tree[i+d-2],p-m+1,min(n,p),i);
}
}
}
}
cout<<ans;
return 0;
}
Compilation message
walls.cpp: In function 'int main()':
walls.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&n,&m,&d,&t);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
20 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
15 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
20 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
