Submission #307467

#	Time	Username	Problem	Language	Result	Execution time	Memory
307467		Akashi	Pairs (IOI07_pairs)	C++14	100 / 100	382 ms	46328 KiB

pairs

#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 (stderr)

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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10