Submission #675950

#	Time	Username	Problem	Language	Result	Execution time	Memory
675950		onlk97	Pairs (IOI07_pairs)	C++14	100 / 100	420 ms	64072 KiB

pairs

#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 / 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