oj.uz

Submission #677058

# Submission time Handle Problem Language Result Execution time Memory
677058 2023-01-02T08:05:13 Z tommy1024 Pairs (IOI07_pairs) C++17
52 / 100
 193 ms 24536 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,p[h].d2+D);
            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,M),p3[h].d3-D,min(p3[h].d3+D,M),p3[h].d4-D,min(p3[h].d4+D,M));
            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 1 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 17 ms 920 KB Output is correct
2 Correct 15 ms 864 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 988 KB Output is correct
2 Correct 23 ms 888 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 988 KB Output is correct
2 Correct 25 ms 884 KB Output is correct
3 Correct 26 ms 896 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 32 ms 1348 KB Output is correct
2 Correct 34 ms 1348 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1320 KB Output is correct
2 Correct 32 ms 1324 KB Output is correct
3 Correct 34 ms 1420 KB Output is correct
4 Correct 33 ms 1244 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1872 KB Output is correct
2 Incorrect 47 ms 1880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 11984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 2868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 191 ms 17228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 24536 KB Output isn't correct
2 Halted 0 ms 0 KB -