oj.uz

Submission #677060

# Submission time Handle Problem Language Result Execution time Memory
677060 2023-01-02T08:08:03 Z tommy1024 Pairs (IOI07_pairs) C++17
100 / 100
 243 ms 24396 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
int B,N,D,M;
int arr[100005];
int tree[150005];
int tree3[226][226][226];
ll ans;
struct point{
    int d1,d2;
    bool operator<(const point &r)const{
        return d1<r.d1;
    }
}p[100005];
struct point3{
    int d1,d2,d3,d4;
    bool operator<(const point3 &r)const{
        return d1<r.d1;
    }
}p3[100005];
void update(int x,int val){
    while(x<=150000){
        tree[x]+=val;
        x+=x&-x;
    }
}
void update3(int x,int y,int z,int val){
    while(x<=225){
        int Y=y;
        while(Y<=225){
            int Z=z;
            while(Z<=225){
                tree3[x][Y][Z]+=val;
                Z+=Z&-Z;
            }
            Y+=Y&-Y;
        }
        x+=x&-x;
    }
}
ll sum(int x){
    ll ret=0;
    while(x>0){
        ret+=tree[x];
        x-=x&-x;
    }
    return ret;
}
ll sum3(int x,int y,int z){
    ll ret=0;
    while(x>0){
        int Y=y;
        while(Y>0){
            int Z=z;
            while(Z>0){
                ret+=tree3[x][Y][Z];
                Z-=Z&-Z;
            }
            Y-=Y&-Y;
        }
        x-=x&-x;
    }
    return ret;
}
ll query(int x,int y){
    return sum(y)-sum(x-1);
}
ll query3(int x1,int x2,int y1,int y2,int z1,int z2){
    ll ret=sum3(x2,y2,z2)-sum3(x1-1,y2,z2)-sum3(x2,y1-1,z2)-sum3(x2,y2,z1-1);
    ret+=sum3(x1-1,y1-1,z2)+sum3(x1-1,y2,z1-1)+sum3(x2,y1-1,z1-1)-sum3(x1-1,y1-1,z1-1);
    return ret;
}
int main()
{
    scanf("%d%d%d%d",&B,&N,&D,&M);
    if(B==1){
        for(int i=1;i<=N;i++){
            scanf("%d",&arr[i]);
        }
        sort(arr+1,arr+N+1);
        int t=1;
        for(int h=1;h<=N;h++){
            while(t<h&&arr[h]-arr[t]>D)t++;
            ans+=h-t;
        }
    }
    else if(B==2){
        for(int i=1;i<=N;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            p[i]={a+b,a-b+75000};
        }
        sort(p+1,p+N+1);
        int t=1;
        for(int h=1;h<=N;h++){
            while(t<h&&p[h].d1-p[t].d1>D){
                update(p[t].d2,-1);
                t++;
            }
            ans+=query(p[h].d2-D,min(p[h].d2+D,150000));
            update(p[h].d2,1);
        }
    }
    else if(B==3){
        for(int i=1;i<=N;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            p3[i]={a+b+c,a+b-c+75,a-b+c+75,-a+b+c+75};
        }
        sort(p3+1,p3+N+1);
        int t=1;
        for(int h=1;h<=N;h++){
            while(t<h&&p3[h].d1-p3[t].d1>D){
                update3(p3[t].d2,p3[t].d3,p3[t].d4,-1);
                t++;
            }
            ans+=query3(p3[h].d2-D,min(p3[h].d2+D,225),p3[h].d3-D,min(p3[h].d3+D,225),p3[h].d4-D,min(p3[h].d4+D,225));
            update3(p3[h].d2,p3[h].d3,p3[h].d4,1);
        }
    }
    printf("%lld",ans);
    return 0;
}

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d%d%d%d",&B,&N,&D,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |             scanf("%d",&arr[i]);
      |             ~~~~~^~~~~~~~~~~~~~
pairs.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~
pairs.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |             scanf("%d%d%d",&a,&b,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 596 KB Output is correct
2 Correct 16 ms 664 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 640 KB Output is correct
2 Correct 22 ms 676 KB Output is correct
3 Correct 20 ms 652 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1084 KB Output is correct
2 Correct 24 ms 1108 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1008 KB Output is correct
2 Correct 32 ms 1124 KB Output is correct
3 Correct 30 ms 996 KB Output is correct
4 Correct 28 ms 1072 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1612 KB Output is correct
2 Correct 33 ms 1612 KB Output is correct
3 Correct 31 ms 2732 KB Output is correct
4 Correct 32 ms 2644 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11936 KB Output is correct
2 Correct 6 ms 11860 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 2608 KB Output is correct
2 Correct 103 ms 2644 KB Output is correct
3 Correct 114 ms 2620 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 16936 KB Output is correct
2 Correct 169 ms 16960 KB Output is correct
3 Correct 69 ms 16944 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 24396 KB Output is correct
2 Correct 181 ms 24308 KB Output is correct
3 Correct 77 ms 24268 KB Output is correct