Submission #677058

#	Time	Username	Problem	Language	Result	Execution time	Memory
677058		tommy1024	Pairs (IOI07_pairs)	C++17	52 / 100	193 ms	24536 KiB

pairs

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

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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10