제출 #684611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684611		vjudge1	Pairs (IOI07_pairs)	C++17	100 / 100	316 ms	96216 KiB

pairs

#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<ii,ii> iiii;
#define ff first
#define ss second
int B,n,D,M;
const int maxn = 1e5 + 10;
struct sub1
{
    int a[maxn];
    int ans=0LL;
    void xuly()
    {
        for (int i=1; i<=n; i++) cin>>a[i];
        sort(a+1,a+n+1);
        int j=1;
        for (int i=1; i<=n; i++)
        {
            while (j<i&&a[i]-a[j]>D) j++;
            ans+=(i-j);
        }
        cout<<ans<<'\n';
    }
};
sub1 _sub1;

bool cmp(ii x, ii y)
{
    return x.ss-x.ff<y.ss-y.ff;
}
struct sub2
{
    ii a[maxn];
    int ans=0LL;
    int f[150010];
    void update(int x, int val)
    {
        while (x<=2*M)
        {
            f[x]+=val;
            x+=(x&-x);
        }
    }
    int get(int x)
    {
        int temp=0;
        while (x>0)
        {
            temp+=f[x];
            x-=(x&-x);
        }
        return temp;
    }
    int getrange(int l, int r)
    {
        l=max(l,1LL);
        r=min(r,2*M);
        return get(r)-get(l-1);
    }

    void xuly()
    {
        for (int i=1; i<=n; i++) cin>>a[i].ff>>a[i].ss;
        sort(a+1,a+n+1,cmp);
        fill_n(f,2*M+1,0);
        int j=1;
        for (int i=1; i<=n; i++)
        {
            while (j<i&&(a[i].ss-a[i].ff) - (a[j].ss-a[j].ff)>D)
            {
                update(a[j].ff+a[j].ss,-1);
                j++;
            }
            ans+=getrange(a[i].ff+a[i].ss-D,a[i].ff+a[i].ss+D);
            update(a[i].ff+a[i].ss,1);
        }
        cout<<ans<<'\n';
    }
};
sub2 _sub2;


struct sub3
{
    iiii a[maxn];
    int ans=0LL;
    int f[226][226][226];
    void update(int x, int y, int z, int val)
    {
        y+=M;
        z+=M;
//        cout<<"+ "<<x<<' '<<y<<' '<<z<<" "<<val<<'\n';
        while (x<=3*M)
        {
            int yy=y;
            while (yy<=3*M)
            {
                int zz=z;
                while (zz<=3*M)
                {
                    f[x][yy][zz]+=val;
                    zz+=(zz&-zz);
                }
                yy+=(yy&-yy);
            }
            x+=(x&-x);
        }
    }
    int get(int x, int y, int z)
    {
        int temp=0;
        while (x>0)
        {
            int yy=y;
            while (yy>0)
            {
                int zz=z;
                while (zz>0)
                {
                    temp+=f[x][yy][zz];
                    zz-=(zz&-zz);
                }
                yy-=(yy&-yy);
            }
            x-=(x&-x);
        }
        return temp;
    }
    int getrange(int l1, int r1, int l2, int r2, int l3, int r3) /** ff+ss+tt; ff-ss+tt ff+ss-tt **/
    {
        l2+=M;
        r2+=M;
        l3+=M;
        r3+=M;
        l1=max(l1,1LL); r1=min(r1,3*M);
        l2=max(l2,1LL); r2=min(r2,3*M);
        l3=max(l3,1LL); r3=min(r3,3*M);
//        cout<<"? "<<l1<<' '<<r1<<" , "<<l2<<' '<<r2<<" , "<<l3<<' '<<r3<<'\n';
//////        cout<<get(r1,r2,r3)<<" - "<<get(l1-1,r2,r3)<<" - "<<get(r1,l2-1,r3)<<" - "<<get(r1,r2,l3-1)<<" + "<<get(l1-1,l2-1,r3)<<" + "<<get(l1-1,r2,l3-1)<<" + "<<get(r1,l2-1,l3-1)<<" - "<<get(l1-1,l2-2,l3-1)<<'\n';
        return get(r1,r2,r3) - get(l1-1,r2,r3) - get(r1,l2-1,r3) - get(r1,r2,l3-1) + get(l1-1,l2-1,r3) + get(l1-1,r2,l3-1) + get(r1,l2-1,l3-1) - get(l1-1,l2-1,l3-1);
    }

    void xuly()
    {
        for (int i=1; i<=n; i++)
        {
            int x,y,z; cin>>x>>y>>z;
            a[i]={{x-y-z,x+y+z},{x-y+z,x+y-z}};
        }
        sort(a+1,a+n+1);
        memset(f,0,sizeof(f));
        int j=1;
        for (int i=1; i<=n; i++)
        {
//            cout<<i<<": "<<a[i].ff.ff<<' '<<a[i].ff.ss<<' '<<a[i].ss.ff<<' '<<a[i].ss.ss<<'\n';
            while (j<i&&a[i].ff.ff-a[j].ff.ff>D)
            {
                update(a[j].ff.ss,a[j].ss.ff,a[j].ss.ss,-1);
                j++;
            }
            ans+=getrange(a[i].ff.ss-D,a[i].ff.ss+D,a[i].ss.ff-D,a[i].ss.ff+D,a[i].ss.ss-D,a[i].ss.ss+D);
            update(a[i].ff.ss,a[i].ss.ff,a[i].ss.ss,1);
//            cout<<ans<<'\n';
        }
        cout<<ans<<'\n';
    }
};
sub3 _sub3;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>B>>n>>D>>M;
    if (B==1) _sub1.xuly();
    else if (B==2) _sub2.xuly();
    else _sub3.xuly();
}

/**

1 6 5 100
25
50
50
10
20
23

4
--------------

2 5 4 10
5 2
7 2
8 4
6 5
4 4

8
--------------

3 8 10 20
10 10 10
10 10 20
10 20 10
10 20 20
20 10 10
20 10 20
20 20 10
20 20 20

12
**/

• 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