Submission #1285589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285589		HoriaHaivas	Pairs (IOI07_pairs)	C++20	60 / 100	3073 ms	31836 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;
    int z;
};

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

class MST
{
public:
    vector<int> aint[600005];
    void build(int l, int r, int val, int nivel)
    {
        if (l==r)
        {
            for (auto z : x[nivel][l])
                aint[val].push_back(z);///SORTEAZA X INAINTE
            return;
        }
        int mid;
        mid=(l+r)/2;
        build(l,mid,val*2,nivel);
        build(mid+1,r,val*2+1,nivel);
        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[2];

class MST2
{
public:
    vector<int> aint[80];
    void build(int l, int r, int val, int nivel)
    {
        if (l==r)
        {
            for (auto z : x[nivel][l])
                aint[val].push_back(z);///SORTEAZA X INAINTE
            return;
        }
        int mid;
        mid=(l+r)/2;
        build(l,mid,val*2,nivel);
        build(mid+1,r,val*2+1,nivel);
        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<<10);
            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;
    }
} griezmann[80];

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,l,r,pas,lim,qa,qb,cx,cy,cd,j;
    long long ans;
    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[1][v[i].x].push_back(v[i].y);
        }
        for (i=1; i<=2*m; i++)
            sort(x[1][i].begin(),x[1][i].end());
        mbappe[1].build(1,2*m,1,1);
        ans=0;
        for (i=1; i<=n; i++)
        {
            qa=max(1,v[i].x-d);
            qb=min(2*m,v[i].x+d);
            r=mbappe[1].query(1,2*m,1,qa,qb,v[i].y+d+1);
            l=mbappe[1].query(1,2*m,1,qa,qb,v[i].y-d);
            ans+=r-l-1;
        }
        cout << ans/2;
    }
    else
    {
        for(i=1; i<=n; i++)
        {
            cin >> v[i].x >> v[i].y >> v[i].z;
            cx=v[i].x;
            cy=v[i].y;
            v[i].x=cx+cy;
            v[i].y=cx-cy;
            x[v[i].z][v[i].x].push_back(v[i].y);
        }
        for (j=1; j<=m; j++)
        {
            for (i=1; i<=2*m; i++)
                sort(x[j][i].begin(),x[j][i].end());
        }
        for (j=1; j<=m; j++)
            griezmann[j].build(1,2*m,1,j);
        ans=0;
        cd=d;
        for (i=1; i<=n; i++)
        {
            d=cd;
            qa=max(1,v[i].x-d);
            qb=min(2*m,v[i].x+d);
            r=griezmann[v[i].z].query(1,2*m,1,qa,qb,v[i].y+d+1);
            l=griezmann[v[i].z].query(1,2*m,1,qa,qb,v[i].y-d);
            ans+=r-l-1;
            for (j=v[i].z-1; j>=1 && d>=1; j--)
            {
                d--;
                qa=max(1,v[i].x-d);
                qb=min(2*m,v[i].x+d);
                r=griezmann[j].query(1,2*m,1,qa,qb,v[i].y+d+1);
                l=griezmann[j].query(1,2*m,1,qa,qb,v[i].y-d);
                ans+=r-l;
            }
            d=cd;
            for (j=v[i].z+1;j<=m && d>=1;j++)
            {
                d--;
                qa=max(1,v[i].x-d);
                qb=min(2*m,v[i].x+d);
                r=griezmann[j].query(1,2*m,1,qa,qb,v[i].y+d+1);
                l=griezmann[j].query(1,2*m,1,qa,qb,v[i].y-d);
                ans+=r-l;
            }
        }
        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