oj.uz

Submission #675950

# Submission time Handle Problem Language Result Execution time Memory
675950 2022-12-28T14:52:17 Z onlk97 Pairs (IOI07_pairs) C++14
100 / 100
 420 ms 64072 KB 
#include <bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
#define dbg(A) cout<<(#A)<<" has value "<<A<<'\n';
#define dbgv(A) cout<<(#A)<<" has values ";for(auto i:A)cout<<i<<' ';cout<<'\n';
#define dbgp(A) cout<<(#A)<<" has values ";for(auto i:A)cout<<i.first<<", "<<i.second<<"   ";cout<<'\n';
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
using qii=pair <pii,pii>;
mt19937 mt(time(nullptr));
int bit1[500000];
void update1(int pos,int val){
    for (int i=pos; i<500000; i+=i&(-i)) bit1[i]+=val;
}
int query1(int pos){
    int ans=0;
    for (int i=pos; i; i-=i&(-i)) ans+=bit1[i];
    return ans;
}
int bit2[310][310][310];
void update2(int xp,int yp,int zp,int val){
    for (int i=xp; i<310; i+=i&(-i)){
        for (int j=yp; j<310; j+=j&(-j)){
            for (int k=zp; k<310; k+=k&(-k)) bit2[i][j][k]+=val;
        }
    }
}
int query(int xp,int yp,int zp){
    int ans=0;
    for (int i=xp; i; i-=i&(-i)){
        for (int j=yp; j; j-=j&(-j)){
            for (int k=zp; k; k-=k&(-k)) ans+=bit2[i][j][k];
        }
    }
    return ans;
}
int query2(int xs,int ys,int zs,int xe,int ye,int ze){
    return query(xe,ye,ze)-query(xs-1,ye,ze)-query(xe,ys-1,ze)-query(xe,ye,zs-1)+query(xs-1,ys-1,ze)+query(xs-1,ye,zs-1)+query(xe,ys-1,zs-1)-query(xs-1,ys-1,zs-1);
}
void solve(){
    int b,n,d,m;
    cin>>b>>n>>d>>m;
    if (b==1){
        int a[n+1];
        for (int i=1; i<=n; i++) cin>>a[i];
        sort(a+1,a+n+1);
        int ans=0,ptr=1;
        for (int i=1; i<=n; i++){
            while (a[i]-a[ptr]>d) ptr++;
            ans+=i-ptr;
        }
        cout<<ans<<'\n';
        return;
    }
    if (b==2){
        d=min(d,150000ll);
        pii a[n+1];
        for (int i=1; i<=n; i++){
            int u,v; cin>>u>>v;
            a[i]={u-v,u+v};
        }
        sort(a+1,a+n+1);
        int ans=0,ptr=1;
        for (int i=1; i<=n; i++){
            while (a[i].x-a[ptr].x>d){
                update1(160000+a[ptr].y,-1);
                ptr++;
            }
            ans+=query1(160000+a[i].y+d)-query1(159999+a[i].y-d);
            update1(160000+a[i].y,1);
        }
        cout<<ans<<'\n';
        return;
    }
    if (b==3){
        d=min(d,225ll);
        qii a[n+1];
        for (int i=1; i<=n; i++){
            int u,v,w; cin>>u>>v>>w;
            a[i]={{u-v-w,u-v+w+76},{u+v-w+76,u+v+w}};
        }
        sort(a+1,a+n+1);
        int ans=0,ptr=1;
        for (int i=1; i<=n; i++){
            while (a[i].x.x-a[ptr].x.x>d){
                update2(a[ptr].x.y,a[ptr].y.x,a[ptr].y.y,-1);
                ptr++;
            }
            ans+=query2(max(1ll,a[i].x.y-d),max(1ll,a[i].y.x-d),max(1ll,a[i].y.y-d),min(309ll,a[i].x.y+d),min(309ll,a[i].y.x+d),min(309ll,a[i].y.y+d));
            update2(a[i].x.y,a[i].y.x,a[i].y.y,1);
        }
        cout<<ans<<'\n';
    }
}
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t=1;
//	cin>>t;
	while (t--) solve();
}

Subtask #1
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1872 KB Output is correct
2 Correct 16 ms 1864 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1972 KB Output is correct
2 Correct 16 ms 1872 KB Output is correct
3 Correct 16 ms 1876 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2388 KB Output is correct
2 Correct 24 ms 2392 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2652 KB Output is correct
2 Correct 31 ms 2628 KB Output is correct
3 Correct 26 ms 2656 KB Output is correct
4 Correct 30 ms 2632 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4048 KB Output is correct
2 Correct 30 ms 4048 KB Output is correct
3 Correct 30 ms 4048 KB Output is correct
4 Correct 29 ms 4036 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23380 KB Output is correct
2 Correct 10 ms 23392 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 6000 KB Output is correct
2 Correct 88 ms 6032 KB Output is correct
3 Correct 75 ms 6032 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 43868 KB Output is correct
2 Correct 218 ms 44004 KB Output is correct
3 Correct 106 ms 43988 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 63984 KB Output is correct
2 Correct 271 ms 64072 KB Output is correct
3 Correct 136 ms 64008 KB Output is correct