Submission #1285575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285575		HoriaHaivas	Pairs (IOI07_pairs)	C++20	60 / 100	332 ms	40916 KiB

pairs

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}


struct nush
{
    int x;
    int y;
};

nush v[100005];
int a[100005];
vector<int> x[150005];///pentru fiecare x, avem y-urile care apar

class MST
{
public:
    vector<int> aint[600005];
    void build(int l, int r, int val)
    {
        if (l==r)
        {
            for (auto z : x[l])
                aint[val].push_back(z);///SORTEAZA X INAINTE
            return;
        }
        int mid;
        mid=(l+r)/2;
        build(l,mid,val*2);
        build(mid+1,r,val*2+1);
        int il,ir,lv,rv;
        il=0;
        ir=0;
        while (il<aint[val*2].size() && ir<aint[val*2+1].size())
        {
            lv=aint[val*2][il];
            rv=aint[val*2+1][ir];
            if (lv<rv)
            {
                aint[val].push_back(lv);
                il++;
            }
            else
            {
                aint[val].push_back(rv);
                ir++;
            }
        }
        while (il<aint[val*2].size())
        {
            lv=aint[val*2][il];
            aint[val].push_back(lv);
            il++;
        }
        while (ir<aint[val*2+1].size())
        {
            rv=aint[val*2+1][ir];
            aint[val].push_back(rv);
            ir++;
        }
    }

    int query(int l, int r, int val, int qa, int qb, int x)///strict mai mic
    {
        if (qa<=l && r<=qb)
        {
            int r,pas;
            r=-1;
            pas=(1<<17);
            while (pas)
            {
                if (r+pas<aint[val].size() && aint[val][r+pas]<x)
                    r+=pas;
                pas=pas/2;
            }
            return r+1;
        }
        int mid,ans;
        ans=0;
        mid=(l+r)/2;
        if (qa<=mid)
            ans+=query(l,mid,val*2,qa,qb,x);
        if (qb>mid)
            ans+=query(mid+1,r,val*2+1,qa,qb,x);
        return ans;
    }
} mbappe;

signed main()
{
    /*
    ifstream fin("camere.in");
    ofstream fout("camere.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int b,n,m,d,i,ans,l,r,pas,lim,qa,qb,cx,cy;
    cin >> b >> n >> d >> m;
    if (b==1)
    {
        for (i=1; i<=n; i++)
        {
            cin >> a[i];
        }
        sort(a+1,a+1+n);
        ans=0;
        for (i=1; i<=n; i++)
        {
            l=0;
            lim=a[i]-d;
            pas=(1<<17);
            while (pas)
            {
                if (l+pas<=n && a[l+pas]<lim)
                    l+=pas;
                pas=pas/2;
            }
            l++;
            r=0;
            lim=a[i]+d;
            pas=(1<<17);
            while (pas)
            {
                if (r+pas<=n && a[r+pas]<=lim)
                    r+=pas;
                pas=pas/2;
            }
            ans+=r-l+1-1;
        }
        cout << ans/2;
    }
    else if (b==2)///de aici incepe nebunia
    {
        for (i=1;i<=n;i++)
        {
             cin >> v[i].x >> v[i].y;
             cx=v[i].x;
             cy=v[i].y;
             v[i].x=cx+cy;
             v[i].y=cx-cy;
             x[v[i].x].push_back(v[i].y);
        }
        for (i=1;i<=2*m;i++)
             sort(x[i].begin(),x[i].end());
        mbappe.build(1,2*m,1);
        ans=0;
        for (i=1;i<=n;i++)
        {
             qa=max(1LL,v[i].x-d);
             qb=min(2*m,v[i].x+d);
             r=mbappe.query(1,2*m,1,qa,qb,v[i].y+d+1);
             l=mbappe.query(1,2*m,1,qa,qb,v[i].y-d);
             ans+=r-l-1;
        }
        cout << ans/2;
    }
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10