oj.uz

답안 #684611

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684611 2023-01-22T01:53:08 Z vjudge1 Pairs (IOI07_pairs) C++17
100 / 100
 316 ms 96216 KB 
#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.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 6100 KB Output is correct
2 Correct 14 ms 6100 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 6604 KB Output is correct
2 Correct 19 ms 6676 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 6588 KB Output is correct
2 Correct 18 ms 6632 KB Output is correct
3 Correct 23 ms 6700 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6200 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 5588 KB Output is correct
2 Correct 20 ms 5588 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 5804 KB Output is correct
2 Correct 26 ms 5796 KB Output is correct
3 Correct 25 ms 5792 KB Output is correct
4 Correct 24 ms 5788 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 7180 KB Output is correct
2 Correct 38 ms 7192 KB Output is correct
3 Correct 29 ms 7192 KB Output is correct
4 Correct 29 ms 7164 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 95308 KB Output is correct
2 Correct 36 ms 95308 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 95980 KB Output is correct
2 Correct 77 ms 95892 KB Output is correct
3 Correct 73 ms 95948 KB Output is correct

Subtask #12
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 96204 KB Output is correct
2 Correct 230 ms 96108 KB Output is correct
3 Correct 105 ms 96200 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 287 ms 96212 KB Output is correct
2 Correct 316 ms 96216 KB Output is correct
3 Correct 97 ms 96208 KB Output is correct