oj.uz

Submission #335579

# Submission time Handle Problem Language Result Execution time Memory
335579 2020-12-13T08:42:16 Z Joshc Pairs (IOI07_pairs) C++11
100 / 100
 315 ms 25488 KB 
#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

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.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1384 KB Output is correct
2 Correct 18 ms 1384 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1640 KB Output is correct
2 Correct 27 ms 1768 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1768 KB Output is correct
2 Correct 26 ms 1768 KB Output is correct
3 Correct 23 ms 1768 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2148 KB Output is correct
2 Correct 32 ms 2020 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2276 KB Output is correct
2 Correct 38 ms 2276 KB Output is correct
3 Correct 37 ms 2276 KB Output is correct
4 Correct 37 ms 2084 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2912 KB Output is correct
2 Correct 42 ms 2912 KB Output is correct
3 Correct 42 ms 2912 KB Output is correct
4 Correct 41 ms 2912 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11884 KB Output is correct
2 Correct 7 ms 11884 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3168 KB Output is correct
2 Correct 65 ms 3168 KB Output is correct
3 Correct 68 ms 3168 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 17628 KB Output is correct
2 Correct 211 ms 17756 KB Output is correct
3 Correct 100 ms 17628 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 25416 KB Output is correct
2 Correct 260 ms 25436 KB Output is correct
3 Correct 121 ms 25488 KB Output is correct