Submission #104651

#	Time	Username	Problem	Language	Result	Execution time	Memory
104651		knon0501	방벽 (JOI15_walls)	C++14	0 / 100	20 ms	512 KiB

walls

#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 (stderr)

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);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 45
• Subtask 3: 0 / 45