Submission #1053928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053928		Dennis_Jason	Pairs (IOI07_pairs)	C++14	30 / 100	4059 ms	4188 KiB

pairs

#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
                {
                    st=mid+1;
                }
            }
                if(x_axis==-1)
                {
                    seg.update(v[i].d2,1);
                    continue;
                }
                for(int j=1;j<x_axis;++j)
                    seg.update(v[j].d2,0);

            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 (stderr)

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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10