oj.uz

Submission #482558

# Submission time Handle Problem Language Result Execution time Memory
482558 2021-10-25T14:55:54 Z nicolaalexandra Pairs (IOI07_pairs) C++14
85 / 100
 379 ms 16724 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 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 332 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1708 KB Output is correct
2 Correct 32 ms 1740 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1672 KB Output is correct
2 Correct 44 ms 1740 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1760 KB Output is correct
2 Correct 47 ms 1700 KB Output is correct
3 Correct 47 ms 1776 KB Output is correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1784 KB Output is correct
2 Correct 42 ms 1748 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1696 KB Output is correct
2 Correct 52 ms 1732 KB Output is correct
3 Correct 53 ms 1848 KB Output is correct
4 Correct 57 ms 1732 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 2160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14636 KB Output is correct
2 Correct 12 ms 14748 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2060 KB Output is correct
2 Correct 43 ms 2244 KB Output is correct
3 Correct 45 ms 2324 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 11240 KB Output is correct
2 Correct 257 ms 11676 KB Output is correct
3 Correct 96 ms 11608 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 16208 KB Output is correct
2 Correct 379 ms 16724 KB Output is correct
3 Correct 119 ms 16688 KB Output is correct