Submission #482533

#	Time	Username	Problem	Language	Result	Execution time	Memory
482533		nicolaalexandra	Pairs (IOI07_pairs)	C++14	45 / 100	278 ms	16636 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);
}
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-1,m-x+y,z};
        sp[z][v[i].x][v[i].y]++;
    }

    for (i=1;i<=m;i++)
        for (j=1;j<=2*m;j++)
            for (k=1;k<=2*m;k++)
                sp[i][j][k] += sp[i][j-1][k] + sp[i][j][k-1] - sp[i][j-1][k-1];

    long long ans = 0;
    for (i=1;i<=n;i++){
        x = v[i].x, y = v[i].y;
        for (z=1;z<=m;z++){
            if (z == 10 || z == 20)
                z = z;
            int val = d - modul (z - v[i].z);
            if (val < 0)
                continue;
            ans += sp[z][x][y] - sp[z][max(0,x-val-1)][y] - sp[z][x][max(0,y-val-1)] + sp[z][max(0,x-val-1)][max(0,y-val-1)];
        }
    }

    cout<<ans - n;


    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: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10