oj.uz

Submission #587412

# Submission time Handle Problem Language Result Execution time Memory
587412 2022-07-01T20:17:52 Z Bench0310 Pairs (IOI07_pairs) C++17
100 / 100
 212 ms 25268 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 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 340 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2276 KB Output is correct
2 Correct 21 ms 2276 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2772 KB Output is correct
2 Correct 24 ms 2664 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2656 KB Output is correct
2 Correct 22 ms 2664 KB Output is correct
3 Correct 23 ms 2664 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 34 ms 2516 KB Output is correct
2 Correct 28 ms 2476 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2660 KB Output is correct
2 Correct 32 ms 2664 KB Output is correct
3 Correct 36 ms 2652 KB Output is correct
4 Correct 31 ms 2660 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3556 KB Output is correct
2 Correct 32 ms 3544 KB Output is correct
3 Correct 39 ms 3552 KB Output is correct
4 Correct 33 ms 3560 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11712 KB Output is correct
2 Correct 5 ms 11732 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 3256 KB Output is correct
2 Correct 96 ms 3272 KB Output is correct
3 Correct 115 ms 3332 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 17740 KB Output is correct
2 Correct 172 ms 17728 KB Output is correct
3 Correct 68 ms 17740 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 25268 KB Output is correct
2 Correct 182 ms 25164 KB Output is correct
3 Correct 78 ms 25176 KB Output is correct