oj.uz

Submission #379297

# Submission time Handle Problem Language Result Execution time Memory
379297 2021-03-17T22:52:37 Z MilosMilutinovic Pairs (IOI07_pairs) C++14
100 / 100
 379 ms 27500 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,d,m;
void Solve1D(){
    vector<int> x(n);
    for(int i=0;i<n;i++)scanf("%i",&x[i]);
    sort(x.begin(),x.end());
    ll ans=0;
    for(int i=0;i<n;i++){
        int bot=i,top=n-1,pos=i;
        while(bot<=top){
			int mid=bot+top>>1;
            if(x[mid]-x[i]<=d)pos=mid,bot=mid+1;
            else top=mid-1;
        }
        ans+=pos-i;
    }
    printf("%lld",ans);
}
const int N=200050;
int x[N],y[N],sum[N],dif[N],id[N];
int bit[N];
void Add(int x,int f){for(;x<N;x+=x&-x)bit[x]+=f;}
int Get(int x){int res=0;for(;x;x-=x&-x)res+=bit[x];return res;}
void Solve2D(){
    for(int i=0;i<n;i++)scanf("%i%i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i],id[i]=i;
    sort(id,id+n,[&](int i,int j){
        return dif[i]<dif[j];
	});
    int j=0;
    ll ans=0;
    for(int i=0;i<n;i++){
        while(dif[id[i]]-dif[id[j]]>d){
            Add(sum[id[j]],-1);
			j++;
        }
        ans+=Get(min(N-1,sum[id[i]]+d))-Get(max(1,sum[id[i]]-d-1));
        Add(sum[id[i]],1);
    }
    printf("%lld",ans);
}
const int H=250;
struct BIT3D{
    int sum[H][H][H];
    void Add(int x,int y,int z,int f){
		for(int i=x;i<H;i+=i&-i){
            for(int j=y;j<H;j+=j&-j){
                for(int k=z;k<H;k+=k&-k){
                    sum[i][j][k]+=f;
                }
            }
		}
    }
    int Get(int x,int y,int z){
        int res=0;
        for(int i=x;i;i-=i&-i){
            for(int j=y;j;j-=j&-j){
                for(int k=z;k;k-=k&-k){
                    res+=sum[i][j][k];
                }
            }
        }
        return res;
    }
    int Get(int xl,int xr,int yl,int yr,int zl,int zr){
        xl--;yl--;zl--;
    	xl=max(xl,0);
        yl=max(yl,0);
        zl=max(zl,0);
        xr=min(xr,H-1);
        yr=min(yr,H-1);
        zr=min(zr,H-1);
        return Get(xr,yr,zr)-Get(xl,yr,zr)-Get(xr,yl,zr)-Get(xr,yr,zl)+Get(xl,yl,zr)+Get(xl,yr,zl)+Get(xr,yl,zl)-Get(xl,yl,zl);
	}
} ST;
int z[N];
void Solve3D(){
    for(int i=1;i<=n;i++)scanf("%i%i%i",&x[i],&y[i],&z[i]),id[i]=i;
    sort(id+1,id+n+1,[&](int i,int j){
        return x[i]+y[i]+z[i]<x[j]+y[j]+z[j];
	});
    int j=1;
    ll ans=0;
    for(int i=1;i<=n;i++){
        int l=id[i];
        while(x[l]+y[l]+z[l]-x[id[j]]-y[id[j]]-z[id[j]]>d){
            int k=id[j];
            ST.Add(m-x[k]+y[k]+z[k],m+x[k]-y[k]+z[k],m+x[k]+y[k]-z[k],-1);
            j++;
        }
        ans+=ST.Get(m-x[l]+y[l]+z[l]-d,m-x[l]+y[l]+z[l]+d,m+x[l]-y[l]+z[l]-d,m+x[l]-y[l]+z[l]+d,m+x[l]+y[l]-z[l]-d,m+x[l]+y[l]-z[l]+d);
		ST.Add(m-x[l]+y[l]+z[l],m+x[l]-y[l]+z[l],m+x[l]+y[l]-z[l],1);
	}
	printf("%lld",ans);
}
int main(){
	int b;scanf("%i%i%i%i",&b,&n,&d,&m);
    if(b==1)Solve1D();
    if(b==2)Solve2D();
    if(b==3)Solve3D();
}

Compilation message

pairs.cpp: In function 'void Solve1D()':
pairs.cpp:13:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |    int mid=bot+top>>1;
      |            ~~~^~~~
pairs.cpp:7:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |     for(int i=0;i<n;i++)scanf("%i",&x[i]);
      |                         ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void Solve2D()':
pairs.cpp:27:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     for(int i=0;i<n;i++)scanf("%i%i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i],id[i]=i;
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'void Solve3D()':
pairs.cpp:79:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |     for(int i=1;i<=n;i++)scanf("%i%i%i",&x[i],&y[i],&z[i]),id[i]=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:98:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |  int b;scanf("%i%i%i%i",&b,&n,&d,&m);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 748 KB Output is correct
2 Correct 27 ms 768 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 748 KB Output is correct
2 Correct 26 ms 768 KB Output is correct
3 Correct 27 ms 748 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2284 KB Output is correct
2 Correct 32 ms 2284 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2284 KB Output is correct
2 Correct 39 ms 2284 KB Output is correct
3 Correct 42 ms 2412 KB Output is correct
4 Correct 45 ms 2284 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2944 KB Output is correct
2 Correct 45 ms 2924 KB Output is correct
3 Correct 46 ms 2796 KB Output is correct
4 Correct 52 ms 2796 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12524 KB Output is correct
2 Correct 8 ms 12524 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3564 KB Output is correct
2 Correct 113 ms 3564 KB Output is correct
3 Correct 85 ms 3568 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 19436 KB Output is correct
2 Correct 275 ms 19308 KB Output is correct
3 Correct 129 ms 19308 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 27500 KB Output is correct
2 Correct 319 ms 27500 KB Output is correct
3 Correct 173 ms 27372 KB Output is correct