oj.uz

Submission #735121

# Submission time Handle Problem Language Result Execution time Memory
735121 2023-05-03T15:03:06 Z huynhyen1609 Pairs (IOI07_pairs) C++14
100 / 100
 301 ms 61676 KB 
/*
                                 ..
                        .:^!7?JJJYJJJJ?77!!~^.
                   .:~7JYYJYYJJ?77?J??JY?JYY5YY?7~:.
                 :!J5YJ??777J?J?????7J?J?7J?J?JYYYYY?~.
               :?5JJ???77!?77?J??J7?7???JJJJ?J777??JYJY?!.
             ^J5YYJJJ77?!7!7!77JJJJ?J77??Y???77!!777!7?JY5?^
           ~JYY??J7??7J?7?!7!7???J?77!777J?JY?J7777?7?????5PY^
         ^Y5J??J??!!???J??77777????J?J77?YY?!~^::::::^!77??YPG7.
        !PY?777?77!7!7J?7!7?????JJ??7J??J^:.           .:!7?75GY:
      .JPJ!7!7?7?7!7!????????J?7??7J?YJ~.                .:!7?JGP^
     .JP?!7!!??7J7!!!?7J????7J7!!?!?7?7.                 .  ^??YG5:
     !P??7777?77??777?7?!7!777!?7J??J?^              :~~:  . ^?7YGY.
    :PY7??77!7~~:::.....:^^~!7??????J?^        .   .7PGGPY: . !?JPB~
   .Y5!!Y77!~:..            .:~7JJJ??J!.       . . .5GGGGP^ ..:J?JBJ
   ~G?!!?7!^.                  .^7JJYYJ7:.      . ..:~???~^^:..77?G5.
   !G!7?77:                     ..?J7~^~!77: .  .. ..^~~~~~~~:.!75B!
   !P77J7^                     ..~?:::^~!7?^ ........^~^^^^^:.^JYG?.
   !G???!:      .~77!:.        ..7?7?77~:....................^JPJ~
   :P5??7:     .JGGGGP!        ......  ..................:^!JP?^
    7BJ7J~     .JGGGGG~       . .....................::::^!7?JJ?!^.
    .YG?Y7^     .~7??~:::.     ..  .... ... ....::::::::::::^?~^!?J7:
     :PPJ??:    ..:^^^^^^:     .  .... ....::::^::::::::.:::^JP~..:75~
      :YGYJ?^.  .^^^^^^^:.        .....:::::::::::...:::..:.::JP!~~7Y~
        ~PP5J?^...::::.... ......::::::::.:.::.:::::.:::::::::^JP?7~.
         :75P5YJ!~^^^^!:...::^:::::::...:......::.....::::::::^^5?
           ?G?Y55PP5YJ!^:::::::::..:..:.:....:...:....::..::::^^7G^
           ~P!^:::::.::::::::::::::...:.::::.:.:::::.:.......:::^PY
            :!JJ7~^::::::::::::::::..:.:.::.:::::...::.........:.JP.
               :5P?^:^:::::^::::::::::::.::::::.:.::.::........::7P:
               .P7::::::::::^::^^::::::::::::::::.:.........:::::J5.
           .   ^G~:^^:::::::^:^^^^^:::::::::^:::::::::::::::^^::75^
               :P!^^^^^^^^:^^^^^^:^:::::^:::^:::::::::::::::^^7JY^
               .!5~^~^^^^^^^^^:^^^^^^^^:^^^^:^^^^^^^^^^^^^^~?55G?
                 ~J?~~~^^~~^~~~^^^^^^^:^^^~^^^^^^^^~~!!!?Y55GP?J!.
                  .~PYJ?77?7777!!!!!!!!!!!!7777??JJJJJ5PP5??J^  ..
                   .777?5J??YYYYY5?7777!!!!~!~~^^::.  .::
                        :!!~:.:^^:

        PENGUIN SO CUTE, I LOVE PENGUIN
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define NAME "disrupt"
#define int long long
#define pii pair<int,int>
const int oo=1e18;
const int mod=1e9+7;
const int N=1e5;
const int LG=18;
const int Sqrt=350;
//int hx[]={0,0,1,-1,1,1,-1,-1},hy[]={1,-1,0,0,1,-1,1,-1};
int b,n,d,m,bit1[150005],bit2[305][305][305];
void up1(int i,int val)
{
    i+=m;
    while(i<=2*m)
    {
        bit1[i]+=val;
        i+=i&-i;
    }
}
int get1(int i)
{
    i+=m;
    int g=0;
    while(i>0)
    {
        g+=bit1[i];
        i-=i&-i;
    }
    return g;
}
void up2(int x,int y,int z,int val)
{
    for(x+=m*2;x<=4*m;x+=x&-x)
        for(int yt=2*m+y;yt<=4*m;yt+=yt&-yt)
            for(int zt=2*m+z;zt<=4*m;zt+=zt&-zt)bit2[x][yt][zt]+=val;
}
int get2(int x,int y,int z)
{
    int g=0;
    for(x+=m*2;x>0;x-=x&-x)
        for(int yt=2*m+y;yt>0;yt-=yt&-yt)
            for(int zt=2*m+z;zt>0;zt-=zt&-zt)g+=bit2[x][yt][zt];
    return g;
}
int sum(int x1,int y1,int z1,int x2,int y2,int z2)
{
    return get2(x1,y1,z1)-get2(x2,y1,z1)-get2(x1,y2,z1)-get2(x1,y1,z2)
            +get2(x2,y2,z1)+get2(x2,y1,z2)+get2(x1,y2,z2)-get2(x2,y2,z2);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen(""NAME".in","r",stdin);
    //freopen(""NAME".out","w",stdout);
    cin>>b>>n>>d>>m;
    if(b==1)
    {
        int a[N+4];
        for(int i=1;i<=n;++i)cin>>a[i];
        sort(a+1,a+n+1);
        int res=0;
        for(int i=1,j=1;i<=n;++i)
        {
            while(a[i]-a[j]>d&&j<i)++j;
            res+=i-j;
        }
        cout<<res;
        return 0;
    }
    if(b==2)
    {
        pii a[N+4];
        for(int i=1;i<=n;++i)
        {
            int x,y;cin>>x>>y;
            a[i]={x+y,x-y};
        }
        sort(a+1,a+n+1);
        int res=0;
        for(int i=1,j=1;i<=n;++i)
        {
            while(a[i].fi-a[j].fi>d&&j<i)
            {
                up1(a[j].se,-1);
                ++j;
            }
            res+=get1(min(m,a[i].se+d))-get1(max(a[i].se-d-1,-m));
            up1(a[i].se,1);
        }
        cout<<res;
        return 0;
    }
    if(b==3)
    {
        pair<pii,pii>a[N+4];
        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);
        int res=0;
        for(int i=1,j=1;i<=n;++i)
        {
            while(a[i].fi.fi-a[j].fi.fi>d&&j<i)
            {
                up2(a[j].fi.se,a[j].se.fi,a[j].se.se,-1);
                ++j;
            }
            res+=sum(min(2*m,a[i].fi.se+d),min(2*m,a[i].se.fi+d),min(2*m,a[i].se.se+d),
                     max(-2*m,a[i].fi.se-d-1),max(-2*m,a[i].se.fi-d-1),max(-2*m,a[i].se.se-d-1));
            up2(a[i].fi.se,a[i].se.fi,a[i].se.se,1);
        }
        cout<<res;
        return 0;
    }
}
/*
         ଘ(੭ˊᵕˋ)੭* ੈ✩‧˚huynhyen1609<3
*/

Compilation message

pairs.cpp:95:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   95 | main()
      | ^~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3456 KB Output is correct
2 Correct 12 ms 3412 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3540 KB Output is correct
2 Correct 16 ms 3412 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3412 KB Output is correct
2 Correct 20 ms 3412 KB Output is correct
3 Correct 16 ms 3460 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3444 KB Output is correct
2 Correct 25 ms 3460 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3532 KB Output is correct
2 Correct 27 ms 3452 KB Output is correct
3 Correct 26 ms 3456 KB Output is correct
4 Correct 28 ms 3476 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4480 KB Output is correct
2 Correct 30 ms 4476 KB Output is correct
3 Correct 31 ms 4472 KB Output is correct
4 Correct 34 ms 4480 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24788 KB Output is correct
2 Correct 11 ms 24916 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4616 KB Output is correct
2 Correct 59 ms 5216 KB Output is correct
3 Correct 35 ms 5204 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 40052 KB Output is correct
2 Correct 207 ms 40996 KB Output is correct
3 Correct 83 ms 40940 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 60744 KB Output is correct
2 Correct 267 ms 61612 KB Output is correct
3 Correct 131 ms 61676 KB Output is correct