oj.uz

Submission #1053927

# Submission time Handle Problem Language Result Execution time Memory
1053927 2024-08-11T21:24:31 Z Dennis_Jason Pairs (IOI07_pairs) C++14
30 / 100
 88 ms 5468 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------------*/
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);
    }
};
int b,n,d,m;
int res;
const int M=75001;
struct point{
    int d1,d2;
};
/*---------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;
}
segtree seg;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    cin>>b>>n>>d>>m;
    if(b==1)
    {
        subtask1();
    }
    else if(b==2)
    {
        vector<point>v(n+1);
        for(int i=1;i<=n;++i)
        {
            int x,y;
            cin>>x>>y;
            v[i]={x+y,x-y};
        }
        auto cmp=[&](point a,point b)
        {
            return a.d1<b.d1;
        };
        sort(v.begin()+1,v.end(),cmp);
        int ans=0;
        seg.init(M);
        for(int i=1;i<=n;++i)
        {
            int st=1;
            int dr=i-1;
            int x_axis=-1;
            while(st<=dr)
            {
                int mid=(st+dr)/2;
                if(abs(v[i].d1-v[mid].d1)<=d)
                {
                    x_axis=mid;
                    dr=mid-1;
                }
                else
                {
                    seg.update(v[mid].d2,0);
                    st=mid+1;
                }
            }
                if(x_axis==-1)
                {
                    seg.update(v[i].d2,1);
                    continue;
                }
            int query_left=max((int)0,v[i].d2-d);
            int query_right=min(M,v[i].d2+d);
           int y_axis=seg.query(query_left,max((int)0,v[i].d2-1))+seg.query(v[i].d2+1,query_right);
            ans+=x_axis-(x_axis-y_axis);
            seg.update(v[i].d2,1);
//            cout<<x_axis<<" "<<y_axis<<"="<<x_axis-(x_axis-y_axis)<<nl;
        }
        cout<<ans;

    }

    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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 12 ms 2008 KB Output is correct
2 Correct 12 ms 1884 KB Output is correct

Subtask #5
6.0 / 6.0

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

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Incorrect 2 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 5468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -