oj.uz

Submission #65136

# Submission time Handle Problem Language Result Execution time Memory
65136 2018-08-06T17:11:16 Z edisonhello Pairs (IOI07_pairs) C++14
100 / 100
 586 ms 29880 KB 
#include<bits/stdc++.h>
using namespace std;

int b,n,d,m;
struct point{
    int x,y,z;
} p[100005];

namespace three_dim{

int pre[77][155][155];

int get(int z,int xl,int xr,int yl,int yr){
    int rt=pre[z][xr][yr];
    if(xl)rt-=pre[z][xl-1][yr];
    if(yl)rt-=pre[z][xr][yl-1];
    if(xl&&yl)rt+=pre[z][xl-1][yl-1];
    return rt;
} 

void solve(){
    int mnx=7575757,mny=7575757,mxx=-7575757,mxy=-7575757;
    for(int i=1;i<=n;++i){
        tie(p[i].x,p[i].y)=make_pair(p[i].x+p[i].y,p[i].x-p[i].y);
        mnx=min(mnx,p[i].x);
        mny=min(mny,p[i].y);
        mxx=max(mxx,p[i].x);
        mxy=max(mxy,p[i].y);
    }
    for(int i=1;i<=n;++i){
        p[i].x-=mnx;
        p[i].y-=mny;
    }
    mxx-=mnx; mxy-=mny;
    mnx=mny=0;
    for(int i=1;i<=n;++i){
        ++pre[p[i].z][p[i].x][p[i].y];
    }
    for(int z=1;z<=75;++z){
        for(int i=0;i<155;++i){
            for(int j=0;j<155;++j){
                if(i)pre[z][i][j]+=pre[z][i-1][j];
                if(j)pre[z][i][j]+=pre[z][i][j-1];
                if(i&&j)pre[z][i][j]-=pre[z][i-1][j-1];
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=n;++i){
        for(int z=1;z<=75;++z){
            if(abs(z-p[i].z)>d)continue;
            int dd=d-abs(z-p[i].z);
            int xl=p[i].x-dd,xr=p[i].x+dd;
            int yl=p[i].y-dd,yr=p[i].y+dd;
            if(xl<0)xl=0; if(yl<0)yl=0;
            if(xr>150)xr=150; if(yr>150)yr=150;
            ans+=get(z,xl,xr,yl,yr);
            // cout<<i<<" "<<ans<<endl;
        }
    }
    // cout<<"ori ans: "<<ans<<endl;
    cout<<(ans-n)/2<<endl;
}}

namespace two_dim{ 
struct node{
    node *l,*r;
    int tot;
    node():l(0),r(0),tot(0){}
} *root;

#define mid ((l+r)>>1)
void build(node *now,int l,int r){
    if(l==r)return;
    build(now->l=new node(),l,mid);
    build(now->r=new node(),mid+1,r);
}
void modify(node *now,int l,int r,int x,int v){
    now->tot+=v;
    if(l==r)return;
    if(x<=mid)modify(now->l,l,mid,x,v);
    else modify(now->r,mid+1,r,x,v);
}
int query(node *now,int l,int r,int ql,int qr){
    if(qr<l || r<ql)return 0;
    if(ql<=l&&r<=qr)return now->tot;
    return query(now->l,l,mid,ql,qr)+query(now->r,mid+1,r,ql,qr);
}

void solve(){
    int mnx=7575757,mny=7575757,mxx=-7575757,mxy=-7575757;
    for(int i=1;i<=n;++i){
        tie(p[i].x,p[i].y)=make_pair(p[i].x+p[i].y,p[i].x-p[i].y);
        mnx=min(mnx,p[i].x);
        mny=min(mny,p[i].y);
        mxx=max(mxx,p[i].x);
        mxy=max(mxy,p[i].y);
    }
    for(int i=1;i<=n;++i){
        p[i].x-=mnx;
        p[i].y-=mny;
        // cout<<p[i].x<<" "<<p[i].y<<endl;
    }
    sort(p+1,p+1+n,[](const point &a,point &b){ return a.x<b.x; });
    // for(int i=1;i<=n;++i)cout<<p[i].x<<" "<<p[i].y<<endl;
    mxx-=mnx; mxy-=mny;
    mnx=mny=0;
    long long ans=0;
    build(root=new node(),0,mxy);
    for(int i=1,lptr=1,rptr=0;i<=n;++i){
        while(rptr<n && p[rptr+1].x-p[i].x<=d){
            ++rptr;
            modify(root,0,mxy,p[rptr].y,1);
        }
        while(p[i].x-p[lptr].x>d){
            modify(root,0,mxy,p[lptr].y,-1);
            ++lptr;
        }
        ans+=query(root,0,mxy,p[i].y-d,p[i].y+d);
    }
    cout<<(ans-n)/2<<endl;
}}

int gd(int i,int j){
    return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)+abs(p[i].z-p[j].z);
}

int main(){
    cin>>b>>n>>d>>m;
    for(int i=1;i<=n;++i){
        if(b>=1)cin>>p[i].x;
        if(b>=2)cin>>p[i].y;
        if(b>=3)cin>>p[i].z;
    }
    /* if(n<=1000){
        int ans=0;
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                if(gd(i,j)<=d)++ans;
            }
        }
        cout<<ans<<endl;
        return 0;
    } */
    if(b==1){
        vector<int> x;
        for(int i=1;i<=n;++i)x.push_back(p[i].x);
        sort(x.begin(),x.end());
        long long ans=0;
        for(int i=0;i<x.size();++i){
            auto it=upper_bound(x.begin(),x.end(),x[i]+d);
            ans+=it-x.begin()-i-1;
        }
        cout<<ans<<endl;
    }
    if(b==2)two_dim::solve();
    if(b==3)three_dim::solve();
}

Compilation message

pairs.cpp: In function 'void three_dim::solve()':
pairs.cpp:55:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if(xl<0)xl=0; if(yl<0)yl=0;
             ^~
pairs.cpp:55:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
             if(xl<0)xl=0; if(yl<0)yl=0;
                           ^~
pairs.cpp:56:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if(xr>150)xr=150; if(yr>150)yr=150;
             ^~
pairs.cpp:56:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
             if(xr>150)xr=150; if(yr>150)yr=150;
                               ^~
pairs.cpp: In function 'int main()':
pairs.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<x.size();++i){
                     ~^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 496 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2720 KB Output is correct
2 Correct 42 ms 3092 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 3920 KB Output is correct
2 Correct 99 ms 4916 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 5820 KB Output is correct
2 Correct 69 ms 6728 KB Output is correct
3 Correct 92 ms 7588 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14944 KB Output is correct
2 Correct 20 ms 14956 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 14956 KB Output is correct
2 Correct 75 ms 14956 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 14956 KB Output is correct
2 Correct 116 ms 14956 KB Output is correct
3 Correct 112 ms 14956 KB Output is correct
4 Correct 101 ms 14956 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 21264 KB Output is correct
2 Correct 300 ms 22384 KB Output is correct
3 Correct 155 ms 23296 KB Output is correct
4 Correct 147 ms 24544 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24544 KB Output is correct
2 Correct 19 ms 24544 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 24544 KB Output is correct
2 Correct 147 ms 24544 KB Output is correct
3 Correct 117 ms 24764 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 25508 KB Output is correct
2 Correct 565 ms 26348 KB Output is correct
3 Correct 216 ms 27180 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 28160 KB Output is correct
2 Correct 586 ms 29108 KB Output is correct
3 Correct 154 ms 29880 KB Output is correct