oj.uz

Submission #1053942

# Submission time Handle Problem Language Result Execution time Memory
1053942 2024-08-11T21:55:37 Z Dennis_Jason Pairs (IOI07_pairs) C++14
37 / 100
 73 ms 7504 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=150001;
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)+(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 min_active=1;
        int last=1;
        for(int i=1;i<=n;++i)
        {
            fout<<v[i].d2<<" ";
            int st=last;
            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=last;j<x_axis;++j)
                {
                    seg.update(v[j].d2,-1);
                }

            last=x_axis;
            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__
      | 
pairs.cpp: In function 'int main()':
pairs.cpp:136:13: warning: unused variable 'min_active' [-Wunused-variable]
  136 |         int min_active=1;
      |             ^~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1116 KB Output is correct
2 Correct 14 ms 1116 KB Output is correct
3 Correct 13 ms 1116 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
0 / 7.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 7220 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 344 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 348 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 344 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -