oj.uz

Submission #1055509

# Submission time Handle Problem Language Result Execution time Memory
1055509 2024-08-12T20:32:55 Z Dennis_Jason Pairs (IOI07_pairs) C++14
100 / 100
 206 ms 93604 KB 
#include <bits/stdc++.h>
#define NMAX 100001
#define int long long
#define pb push_back
#define eb emplace_back
#define MOD 1000000007
#define nl '\n'
#define INF  1000000007
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int,int>
//#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
 *
 *
    ----------------DEMONSTRATION-------------------

    ---------------------END------------------------

 */
/*-------------Initialize------------*/
const int M=150001;
const int MD=170;
class segtree{
private:
    int n;
    vector<int>tree;
public:
    void init(int sz)
    {
        n=sz;
        tree.resize(4*sz+1);
    }
    void update(int node,int st,int dr,int pos,int val)
    {
        if(st==dr)
        {
            tree[node]+=val;
            return;
        }
        int mid=(st+dr)/2;
        if(pos<=mid)
            update(2*node,st,mid,pos,val);
        else
            update(2*node+1,mid+1,dr,pos,val);
        tree[node]=tree[2*node]+tree[2*node+1];
    }
    int query(int node,int st,int dr,int L,int R)
    {
        if(R<st || dr<L)
            return 0;
        if(L<=st && dr<=R)
        {
            return tree[node];
        }
        int mid=(st+dr)/2;
        int left=query(2*node,st,mid,L,R);
        int right=query(2*node+1,mid+1,dr,L,R);
        return left+right;
    }
    void update(int pos,int val)
    {
        update(1,0,n,pos,val);
    }
    int query(int L,int R)
    {
        return query(1,0,n,L,R);
    }
};

class fenwick3d{
private:
    int X,Y,Z;
    vector<int>tree;
public:
    void init(int sz)
    {
        tree.resize(225*225*225);
        X=Y=Z=3*sz;
    }
    int & calc( int x, int y, int z )
    {
        return tree[ ((x-1)*Y + (y-1))*Z + (z-1) ];
    }

    void update(int i, int j, int k, int val)
    {
        for(int x = i; x <= X; x += (x & -x))
        {
            for(int y = j; y <= Y; y += (y & -y))
            {
                for(int z = k; z <= Z; z += (z & -z))
                {
                    calc(x,y,z)+= val;
                }
            }
        }
    }

    int query(int i, int j, int k)
    {
        int ans = 0;
        for(int x = i; x > 0; x -= (x & -x))
        {
            for(int y = j; y > 0; y -= (y & -y))
            {
                for(int z = k; z > 0; z -= (z & -z))
                {
                    ans += calc(x,y,z);
                }
            }
        }
        return ans;
    }

    int query(int x1,int y1,int z1,int x2,int y2,int z2)
    {
        --x1;
        --y1;
        --z1;
        if(x1 < 0)
            x1 = 0;
        if(x2 > X)
            x2 = X;
        if(y1 < 0)
            y1 = 0;
        if(y2 > Y)
            y2 = Y;
        if(z1 < 0)
            z1 = 0;
        if(z2 > Z)
            z2 = Z;

        return query(x2,y2,z2)-query(x1,y2,z2)-query(x2,y1,z2)-query(x2,y2,z1)+query(x1,y1,z2)+query(x1,y2,z1)+query(x2,y1,z1)-query(x1,y1,z1);
    }

};
int b,n,d,m;
int res;

struct point{
    int d1,d2;
};
struct Point{
    int d1,d2,d3,d4;
};
/*---------subtask1-----------*/
void subtask1()
{
    vector<int>v(n+1);
    for(int i=1;i<=n;++i)
    {
        cin>>v[i];
    }
    sort(v.begin()+1,v.end());
    for(int i=1;i<=n;++i)
    {
        int st=i+1;
        int dr=n;
        int ans=-1;
        while(st<=dr)
        {
            int mid=(st+dr)/2;
            if(abs(v[i]-v[mid])<=d)
            {
                ans=mid;
                st=mid+1;
            }
            else
                dr=mid-1;
        }
        if(ans==-1)
            continue;
        res+=(ans-i);
    }
    cout<<res;
}

/*---------subtask2-----------*/
segtree seg;
void subtask2()
{
    vector<point>v(n+1);
    for(int i=1;i<=n;++i)
    {
        int x,y;
        cin>>x>>y;
        v[i]={x+y,(x-y)+(75000)};
    }
    auto cmp=[&](point a,point b)
    {
        return a.d1<b.d1;
    };
    sort(v.begin()+1,v.end(),cmp);
    int ans=0;
    seg.init(M);
    int last=1;
    for(int i=1;i<=n;++i)
    {
        while(abs(v[i].d1-v[last].d1)>d)
        {
            seg.update(v[last].d2,-1);
            last++;
        }
        ans+=seg.query(v[i].d2-d,v[i].d2+d);
        seg.update(v[i].d2,1);
    }
    cout<<ans;
}
fenwick3d fen;
/*---------subtask3-----------*/
void subtask3()
{
    vector<Point>v(n+1);
    for(int i=1;i<=n;++i)
    {
        int x,y,z;
        cin>>x>>y>>z;
        int d1=(x+y+z)-2;
        int d2=(x+y-z)+(m-1);
        int d3=(x-y+z)+(m-1);
        int d4=(x-y-z)+(m+m);
        v[i]={d1,d2,d3,d4};
    }
    auto cmp=[&](Point a,Point b)
    {
        return a.d1<b.d1;
    };
    sort(v.begin()+1,v.end(),cmp);

    fen.init(m);
    int j=1;
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        while(abs(v[i].d1-v[j].d1)>d)
        {
            fen.update(v[j].d2,v[j].d3,v[j].d4,-1);
            j++;
        }
        int x=v[i].d2;
        int y=v[i].d3;
        int z=v[i].d4;
        int count=fen.query(x-d,y-d,z-d,x+d,y+d,z+d);
         ans+=count;
        fen.update(v[i].d2,v[i].d3,v[i].d4,1);
    }
    cout<<ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    cin>>b>>n>>d>>m;
    if(b==1)
    {
        subtask1();
    }
    else if(b==2)
    {
        subtask2();
    }
    else
    {
        subtask3();
    }

    return 0;
}

Compilation message

pairs.cpp:9: warning: "LLONG_MAX" redefined
    9 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from pairs.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      |

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1628 KB Output is correct
2 Correct 9 ms 1628 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1884 KB Output is correct
2 Correct 12 ms 1832 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1884 KB Output is correct
2 Correct 14 ms 1880 KB Output is correct
3 Correct 14 ms 1884 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7004 KB Output is correct
2 Correct 23 ms 7000 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7004 KB Output is correct
2 Correct 37 ms 7092 KB Output is correct
3 Correct 31 ms 7000 KB Output is correct
4 Correct 40 ms 7004 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 7248 KB Output is correct
2 Correct 56 ms 7248 KB Output is correct
3 Correct 38 ms 7588 KB Output is correct
4 Correct 32 ms 7512 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 89424 KB Output is correct
2 Correct 31 ms 89436 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 93068 KB Output is correct
2 Correct 55 ms 93268 KB Output is correct
3 Correct 51 ms 93308 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 93520 KB Output is correct
2 Correct 141 ms 93520 KB Output is correct
3 Correct 69 ms 93592 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 93460 KB Output is correct
2 Correct 175 ms 93448 KB Output is correct
3 Correct 83 ms 93604 KB Output is correct