oj.uz

Submission #697341

# Submission time Handle Problem Language Result Execution time Memory
697341 2023-02-09T10:15:30 Z WongChun1234 Pairs (IOI07_pairs) C++14
70 / 100
 3579 ms 9516 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
ll b,n,d,m,x[N],y[N],z[N],ans;
ll pt=1,psum[150][150][150];
void sub1(){
    for (int i=1;i<=n;i++){
        cin>>x[i];
    }
    sort(x+1,x+1+n);
    for (int i=1;i<=n;i++){
        while (x[pt]<x[i]-d) pt++;
        ans+=i-pt;
    }
    cout<<ans<<"\n";
}
void sub2(){
    for (int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
}
void sub3(){
    for (int i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>z[i];
        psum[x[i]][y[i]][z[i]]++;
    }
    for (int i=1;i<=75;i++) for (int j=1;j<=75;j++) for (int k=1;k<=75;k++) psum[i][j][k]+=psum[i][j][k-1];
    for (int i=1;i<=n;i++){
        for (int xx=max(1LL,x[i]-d);xx<=min(m,x[i]+d);xx++){
            int dx=abs(x[i]-xx);
            for (int yy=max(1LL,y[i]-(d-dx));yy<=min(m,y[i]+(d-dx));yy++){
                int maxdz=d-dx-abs(y[i]-yy);
                ans+=psum[xx][yy][min(m,z[i]+maxdz)]-psum[xx][yy][max(0LL,z[i]-maxdz-1)];
            }
        }
    }
    cout<<(ans-n)/2<<"\n";
}
int main(){
    cin>>b>>n>>d>>m;
    if (b==1) sub1();
    else if (b==2) sub2();
    else if (b==3) sub3();
    else assert(0);
}

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 33 ms 1024 KB Output is correct
2 Correct 28 ms 1108 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1060 KB Output is correct
2 Correct 47 ms 1064 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1092 KB Output is correct
2 Correct 45 ms 1072 KB Output is correct
3 Correct 44 ms 1064 KB Output is correct

Subtask #6
0 / 7.0

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

Subtask #7
0 / 7.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 8.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7224 KB Output is correct
2 Correct 36 ms 7104 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9504 KB Output is correct
2 Correct 77 ms 9492 KB Output is correct
3 Correct 75 ms 9488 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 9512 KB Output is correct
2 Correct 1439 ms 9512 KB Output is correct
3 Correct 1949 ms 9508 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 9512 KB Output is correct
2 Correct 2978 ms 9516 KB Output is correct
3 Correct 3579 ms 9516 KB Output is correct