Submission #587412

#	Time	Username	Problem	Language	Result	Execution time	Memory
587412		Bench0310	Pairs (IOI07_pairs)	C++17	100 / 100	212 ms	25268 KiB

pairs

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N2=150000;
int bit2[N2];
void add2(int i,int d)
{
    for(;i<N2;i=i|(i+1)) bit2[i]+=d;
}
int sum2(int x)
{
    int s=0;
    for(int i=min(x,N2-1);i>=0;i=(i&(i+1))-1) s+=bit2[i];
    return s;
}
int sum2(int l,int r){return sum2(r)-sum2(l-1);}

const int N3=225;
int bit3[N3][N3][N3];
void add3(int x,int y,int z,int d)
{
    for(int i=x;i<N3;i=i|(i+1)) for(int j=y;j<N3;j=j|(j+1)) for(int k=z;k<N3;k=k|(k+1)) bit3[i][j][k]+=d;
}
int sum3(int x,int y,int z)
{
    int s=0;
    for(int i=min(x,N3-1);i>=0;i=(i&(i+1))-1) for(int j=min(y,N3-1);j>=0;j=(j&(j+1))-1) for(int k=min(z,N3-1);k>=0;k=(k&(k+1))-1) s+=bit3[i][j][k];
    return s;
}
int sum3(int li,int lj,int lk,int ri,int rj,int rk)
{
    int s=0;
    for(int m=0;m<8;m++)
    {
        int t=sum3((m&1)?li-1:ri,(m&2)?lj-1:rj,(m&4)?lk-1:rk);
        int c=(m&1)+((m>>1)&1)+((m>>2)&1);
        if((c&1)==0) s+=t;
        else s-=t;
    }
    return s;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int b,n,d,m;
    cin >> b >> n >> d >> m;
    vector<array<int,4>> v(n);
    for(int i=0;i<n;i++)
    {
        int x,y,z;
        if(b==1)
        {
            cin >> x;
            v[i]={x,0,0,0};
        }
        if(b==2)
        {
            cin >> x >> y;
            v[i]={x+y,74999+x-y,0,0};
        }
        if(b==3)
        {
            cin >> x >> y >> z;
            v[i]={x+y+z,73-x+y+z,73+x-y+z,73+x+y-z};
        }
    }
    sort(v.begin(),v.end());
    ll res=0;
    int l=0,r=-1;
    for(int i=0;i<n;i++)
    {
        while(r+1<n&&v[r+1][0]-v[i][0]<=d)
        {
            r++;
            if(b==2) add2(v[r][1],1);
            if(b==3) add3(v[r][1],v[r][2],v[r][3],1);
        }
        while(v[i][0]-v[l][0]>d)
        {
            if(b==2) add2(v[l][1],-1);
            if(b==3) add3(v[l][1],v[l][2],v[l][3],-1);
            l++;
        }
        if(b==1) res+=(r-l+1);
        if(b==2) res+=sum2(v[i][1]-d,v[i][1]+d);
        if(b==3) res+=sum3(v[i][1]-d,v[i][2]-d,v[i][3]-d,v[i][1]+d,v[i][2]+d,v[i][3]+d);
    }
    cout << (res-n)/2 << "\n";
    return 0;
}

• 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: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10