oj.uz

Submission #307467

# Submission time Handle Problem Language Result Execution time Memory
307467 2020-09-28T08:15:16 Z Akashi Pairs (IOI07_pairs) C++14
100 / 100
 382 ms 46328 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e5 + 5;

struct punct {
    int a, b, c, d, p;
    bool operator < (const punct &aux) {
        if (a != aux.a) return a < aux.a;
        if (b != aux.b) return b < aux.b;
        if (c != aux.c) return c < aux.c;
        return d < aux.d;
    }
};

int n, b, d, m;
int ma, mb, mc;
punct a[DIM];

int ***aib;

void update(int x, int y, int z, int val) {
    for (int i = x; i <= ma ; i = i + (i & (-i)))
    for (int j = y; j <= mb ; j = j + (j & (-j)))
    for (int t = z; t <= mc ; t = t + (t & (-t)))
        aib[i][j][t] += val;
}

int query(int x, int y, int z) {
    x = min(x, ma); y = min(y, mb); z = min(z, mc);

    int ans = 0;

    for (int i = x; i > 0 ; i = i - (i & (-i)))
    for (int j = y; j > 0 ; j = j - (j & (-j)))
    for (int t = z; t > 0 ; t = t - (t & (-t)))
        ans += aib[i][j][t];

    return ans;
}

int _query(int a1, int a2, int b1, int b2, int c1, int c2) {
    return query(a2, b2, c2) - query(a2, b2, c1) - query(a2, b1, c2) - query(a1, b2, c2)
         + query(a2, b1, c1) + query(a1, b2, c1) + query(a1, b1, c2) - query(a1, b1, c1);
}

int main()
{
    #ifdef HOME
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif // HOME

    scanf("%d%d%d%d", &b, &n, &d, &m);
    int x, y, z;

    for (int i = 1; i <= n ; ++i) {
        if (b == 1) {
            scanf("%d", &x);
            a[i] = {x, 1, 1, 1};
        } else if (b == 2) {
            scanf("%d%d", &x, &y);
            a[i] = {x + y, x - y, 1, 1};
        } else {
            scanf("%d%d%d", &x, &y, &z);
            a[i] = {x + y + z, x + y - z, x - y + z, x - y - z};
        }
    }

    ma = 1, mb = 1, mc = 1;
    for (int i = 1; i <= n ; ++i) {
        ma = min(ma, a[i].b);
        mb = min(mb, a[i].c);
        mc = min(mc, a[i].d);
    }

    for (int i = 1; i <= n ; ++i)
        a[i].b -= (ma - 1), a[i].c -= (mb - 1), a[i].d -= (mc - 1);

    ma = 1, mb = 1, mc = 1;
    for (int i = 1; i <= n ; ++i) {
        ma = max(ma, a[i].b);
        mb = max(mb, a[i].c);
        mc = max(mc, a[i].d);
    }

    aib = new int**[ma + 1];
    for (int i = 1; i <= ma ; ++i) {
        aib[i] = new int*[mb + 1];
        for (int j = 1; j <= mb ; ++j) {
            aib[i][j] = new int[mc + 1];
            for (int t = 1; t <= mc ; ++t)
                aib[i][j][t] = 0;
        }
    }


    sort(a + 1, a + n + 1);

    int j = 1;
    long long ans = 0;
    for (int i = 1; i <= n ; ++i) {
        while (j <= n && a[j].a + d < a[i].a) update(a[j].b, a[j].c, a[j].d, -1), ++j;
        ans = ans + _query(a[i].b - d - 1, a[i].b + d, a[i].c - d - 1, a[i].c + d, a[i].d - d - 1, a[i].d + d);
        update(a[i].b, a[i].c, a[i].d, 1);
    }

    printf("%lld", ans);

    return 0;
}

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     scanf("%d%d%d%d", &b, &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
pairs.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |             scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
pairs.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |             scanf("%d%d%d", &x, &y, &z);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2688 KB Output is correct
2 Correct 26 ms 2688 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3064 KB Output is correct
2 Correct 33 ms 3068 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3072 KB Output is correct
2 Correct 33 ms 3072 KB Output is correct
3 Correct 39 ms 3192 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2808 KB Output is correct
2 Correct 44 ms 2816 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3252 KB Output is correct
2 Correct 60 ms 3200 KB Output is correct
3 Correct 59 ms 3192 KB Output is correct
4 Correct 59 ms 3200 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 13304 KB Output is correct
2 Correct 165 ms 13304 KB Output is correct
3 Correct 93 ms 13176 KB Output is correct
4 Correct 89 ms 13176 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 35584 KB Output is correct
2 Correct 26 ms 35584 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2944 KB Output is correct
2 Correct 60 ms 2940 KB Output is correct
3 Correct 50 ms 2944 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 25592 KB Output is correct
2 Correct 268 ms 25592 KB Output is correct
3 Correct 102 ms 25592 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 46328 KB Output is correct
2 Correct 382 ms 46328 KB Output is correct
3 Correct 151 ms 46328 KB Output is correct