oj.uz

Submission #482559

# Submission time Handle Problem Language Result Execution time Memory
482559 2021-10-25T14:57:33 Z nicolaalexandra Pairs (IOI07_pairs) C++14
100 / 100
 360 ms 15912 KB 
#include <bits/stdc++.h>
#define DIM 300010
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.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1420 KB Output is correct
2 Correct 39 ms 1416 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1348 KB Output is correct
2 Correct 46 ms 1436 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1472 KB Output is correct
2 Correct 50 ms 1368 KB Output is correct
3 Correct 48 ms 1452 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1384 KB Output is correct
2 Correct 43 ms 1360 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1456 KB Output is correct
2 Correct 57 ms 1412 KB Output is correct
3 Correct 55 ms 1380 KB Output is correct
4 Correct 54 ms 1400 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 1964 KB Output is correct
2 Correct 69 ms 3204 KB Output is correct
3 Correct 68 ms 3048 KB Output is correct
4 Correct 65 ms 3096 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14708 KB Output is correct
2 Correct 14 ms 14760 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1724 KB Output is correct
2 Correct 45 ms 1680 KB Output is correct
3 Correct 53 ms 1752 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 10840 KB Output is correct
2 Correct 276 ms 10776 KB Output is correct
3 Correct 97 ms 10852 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 15912 KB Output is correct
2 Correct 360 ms 15792 KB Output is correct
3 Correct 118 ms 15780 KB Output is correct