Submission #482558

#	Time	Username	Problem	Language	Result	Execution time	Memory
482558		nicolaalexandra	Pairs (IOI07_pairs)	C++14	85 / 100	379 ms	16724 KiB

pairs

#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

struct point{
    int x,y,z;
} v[DIM];

int aib[DIM];
long long sp[80][160][160];

int n,m,c,d,i,j,x,y,z,k;

inline int cmp (point a, point b){
    return a.x < b.x;
}

inline int cmp2 (point a, point b){
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

void update (int p, int val){
    for (;p<=m;p+=(p&-p))
        aib[p] += val;
}

int query (int p){
    if (p <= 0)
        return 0;

    int sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}
long long modul (long long n){
    return max (n,-n);
}

long long get_sum (int idx, int x, int y, int x2, int y2){
    x = max (0,x-1), y = max (0,y-1);
    x2 = min (2*m,x2), y2 = min (2*m,y2);

    return sp[idx][x2][y2] - sp[idx][x][y2] - sp[idx][x2][y] + sp[idx][x][y];
}

int main (){



    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>c>>n>>d>>m;

    if (c == 1){
        for (i=1;i<=n;i++)
            cin>>v[i].x;

        sort (v+1,v+n+1,cmp);

        long long ans = 0;
        for (i=1;i<=n;i++){

            int st = 1, dr = i, sol = 0;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (v[i].x - v[mid].x <= d){
                    sol = mid;
                    dr = mid-1;
                } else st = mid+1;
            }

            ans += i - sol;

        }

        cout<<ans;

        return 0;
    }

    if (c == 2){

        for (i=1;i<=n;i++){
            cin>>x>>y;
            v[i].x = x+y-1;
            v[i].y = m-x+y;
        }
        m *= 2;
        sort (v+1,v+n+1,cmp2);

        int poz = 1;
        long long ans = 0;

        for (i=1;i<=n;i++){

            update (v[i].y,1);

            while (v[poz].x + d < v[i].x){
                update (v[poz].y,-1);
                poz++;
            }

            ans += query (min(m,v[i].y + d)) - query (max(0,v[i].y - d - 1));

        }

        cout<<ans - n;

        return 0;
    }

    for (i=1;i<=n;i++){
        cin>>x>>y>>z;

        v[i] = {x,y-z+m,y+z};
        sp[v[i].x][v[i].y][v[i].z]++;
    }

    for (i=1;i<=m;i++)
        for (j=0;j<=2*m;j++)
            for (k=0;k<=2*m;k++){
                if (j)
                    sp[i][j][k] += sp[i][j-1][k];
                if (k)
                    sp[i][j][k] += sp[i][j][k-1];
                if (j && k)
                    sp[i][j][k] -= sp[i][j-1][k-1];
            }


    long long ans = 0;
    for (i=1;i<=n;i++){

        for (x=1;x<=m;x++){

            int val = d - modul (x - v[i].x);
            if (val < 0)
                continue;
            ans += get_sum (x,v[i].y - val, v[i].z - val, v[i].y + val, v[i].z + val);
            
        }
    }

    cout<<(ans - n)/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: 0 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 0 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10