Submission #335579

#	Time	Username	Problem	Language	Result	Execution time	Memory
335579		Joshc	Pairs (IOI07_pairs)	C++11	100 / 100	315 ms	25488 KiB

pairs

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define f first
#define s second

int bit[150002], bit2[227][227][227], MAX_M;

void update(int x, int d) {
    for (; x<=MAX_M; x+=x&-x) bit[x] += d;
}

int query(int x) {
    x = max(0, min(x, MAX_M));
    int ans = 0;
    for (; x>0; x-=x&-x) ans += bit[x];
    return ans;
}

void update2(int x, int y, int z, int d) {
    for (; x<=MAX_M; x+=x&-x) {
        for (int y1=y; y1<=MAX_M; y1+=y1&-y1) {
            for (int z1=z; z1<=MAX_M; z1+=z1&-z1) bit2[x][y1][z1] += d;
        }
    }
}

int query2(int x, int y, int z) {
    x = max(0, min(x, MAX_M));
    y = max(0, min(y, MAX_M));
    z = max(0, min(z, MAX_M));
    int ans = 0;
    for (; x>0; x-=x&-x) {
        for (int y1=y; y1>0; y1-=y1&-y1) {
            for (int z1=z; z1>0; z1-=z1&-z1) ans += bit2[x][y1][z1];
        }
    }
    return ans;
}

long int get(int x1, int x2, int y1, int y2, int z1, int z2) {
    return query2(x2, y2, z2)-query2(x1-1, y2, z2)-query2(x2, y1-1, z2)-query2(x2, y2, z1-1)+query2(x1-1, y1-1, z2)+query2(x1-1, y2, z1-1)+query2(x2, y1-1, z1-1)-query2(x1-1, y1-1, z1-1);
}

int main() {
    int b, n, d, m, x, y, z, p=0;
    long long ans = 0;
    scanf("%d%d%d%d", &b, &n, &d, &m);
    MAX_M = m*b+1;
    if (b==1) {
        vector<int> v;
        for (int i=0; i<n; i++) {
            scanf("%d", &x);
            v.push_back(x);
        }
        sort(v.begin(), v.end());
        for (int i=0; i<n; i++) {
            while (v[p]+d<v[i]) p++;
            ans += i-p;
        }
    } else if (b==2) {
        vector<pair<int, int> > v;
        for (int i=0; i<n; i++) {
            scanf("%d%d", &x, &y);
            v.emplace_back(x+y, x-y+m+1);
        }
        sort(v.begin(), v.end());
        for (int i=0; i<n; i++) {
            update(v[i].s, 1);
            while (v[p].f+d<v[i].f) update(v[p++].s, -1);
            ans += query(v[i].s+d)-query(v[i].s-d-1)-1;
        }
    } else {
        vector<pair<int, pair<pair<int, int>, int> > > v;
        for (int i=0; i<n; i++) {
            scanf("%d%d%d", &x, &y, &z);
            v.push_back({x+y+z, {{x+y-z+m+1, x-y+z+m+1}, x-y-z+2*m+1}});
        }
        sort(v.begin(), v.end());
        for (int i=0; i<n; i++) {
            update2(v[i].s.f.f, v[i].s.f.s, v[i].s.s, 1);
            while(v[p].f+d<v[i].f) {
                update2(v[p].s.f.f, v[p].s.f.s, v[p].s.s, -1);
                p++;
            }
            ans += get(v[i].s.f.f-d, v[i].s.f.f+d, v[i].s.f.s-d, v[i].s.f.s+d, v[i].s.s-d, v[i].s.s+d)-1;
        }
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

pairs.cpp: In function 'int main()':
pairs.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d%d%d%d", &b, &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
pairs.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |             scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
pairs.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |             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