oj.uz

답안 #1055492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1055492 2024-08-12T20:06:06 Z Dennis_Jason Pairs (IOI07_pairs) C++14
60 / 100
 4000 ms 85584 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 n,m,r;
    int tree[MD][MD][MD];
public:
    void init(int sz)
    {
        memset(tree,0,sizeof(tree));
        n=m=r=sz;
    }

    void update(int i, int j, int k, int val)
    {
        if ((i < 0) || (j < 0) || (i > n) || (j > m) || (k < 0) || (k > r))
            return;
        for(int x = i; x <= n; x += (x & -x))
        {
            for(int y = j; y <= m; y += (y & -y))
            {
                for(int z = k; z <= r; z += (z & -z))
                {
                    tree[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 += tree[x][y][z];
                }
            }
        }
        return ans;
    }


    void update(int x1,int y1,int z1,int x2,int y2,int z2,int val)
    {
        /// Add 1 to the cube from upper-left [x1,y1,z1] to lower-right [x2,y2,z2]
        update(x2,y2,z1,val);
        update(x1-1,y1-1,z2,val);
        update(x1-1,y2,z1-1,val);
        update(x2,y1-1,z1-1,val);
        update(x1-1,y2,z2,-val);
        update(x2,y1-1,z2,-val);
        update(x2,y2,z1-1,-val);
        update(x1-1,y1-1,z1-1,-val);
    }
    int query(int x1,int y1,int z1,int x2,int y2,int z2)
    {
        return query(x2,y2,z1)-query(x1-1,y2,z2)-query(x2,y1-1,z2)-query(x2,y2,z1-1)+query(x1-1,y1-1,z2)+query(x1-1,y2,z1-1)+query(x2,y1-1,z1-1)-query(x1-1,y1-1,z1-1);
    }

};
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)+75;
        int d2=(x+y-z)+75;
        int d3=(x-y+z)+75;
        int d4=(x-y-z)+75;
        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(MD);
    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-1,v[j].d3-1,v[j].d4-1,v[j].d2+1,v[j].d3+1,v[j].d4+1,-1);
            j++;
        }
        int x=v[i].d2-d;
        int y=v[i].d3-d;
        int z=v[i].d4-d;
        int a=v[i].d2+d;
        int b=v[i].d3+d;
        int c=v[i].d4+d;
         int count=fen.query(x,y,z,a,b,c);
//         cout<<count<<nl;
         ans+=count;
        fen.update(v[i].d2-1,v[i].d3-1,v[i].d4-1,v[i].d2+1,v[i].d3+1,v[i].d4+1,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

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

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

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 7260 KB Output is correct
2 Correct 35 ms 7516 KB Output is correct
3 Correct 33 ms 7516 KB Output is correct
4 Correct 38 ms 7260 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 7764 KB Output is correct
2 Correct 53 ms 7768 KB Output is correct
3 Correct 33 ms 7772 KB Output is correct
4 Correct 31 ms 7772 KB Output is correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4075 ms 38748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 42660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4094 ms 42832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 71 ms 85584 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -