oj.uz

Submission #54599

# Submission time Handle Problem Language Result Execution time Memory
54599 2018-07-04T07:43:24 Z imeimi2000 Pairs (IOI07_pairs) C++17
100 / 100
 347 ms 47464 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, d, m;

struct data1 {
    int x[100000];
};

struct data2 {
    int x[100000];
    int y[100000];
    pii ps[100000];
    int seg[150000] = {};
    int mx;
    
    void update(int i, int v) {
        while (i <= mx) {
            seg[i] += v;
            i += i & -i;
        }
    }
    
    int query(int i) {
        int ret = 0;
        while (i) {
            ret += seg[i];
            i -= i & -i;
        }
        return ret;
    }
};

struct data3 {
    int x[100000];
    int y[100000];
    int z[100000];
    int mx;
    
    int seg[224][224][224] = {};
    
    struct point {
        int x, y, z, w;
        point() {}
        point(int x, int y, int z)
         : x(x + y + z - 2), y(x + y - z + m - 1),
          z(x - y + z + m - 1), w(x - y - z + 2 * m) {}
        bool operator<(const point &p) const {
            return w < p.w;
        }
    } ps[100000];
    
    void update(int _x, int _y, int _z, int v) {
        int x, y, z;
        x = _x;
        while (x <= mx) {
            y = _y;
            while (y <= mx) {
                z = _z;
                while (z <= mx) {
                    seg[x][y][z] += v;
                    z += z & -z;
                }
                y += y & -y;
            }
            x += x & -x;
        }
    }
    
    int in(int x) {
        return max(min(x, mx), 0);
    }
    
    int query(int _x, int _y, int _z) {
        int x, y, z, ret = 0;
        x = _x;
        while (x) {
            y = _y;
            while (y) {
                z = _z;
                while (z) {
                    ret += seg[x][y][z];
                    z -= z & -z;
                }
                y -= y & -y;
            }
            x -= x & -x;
        }
        return ret;
    }
};

llong solve1() {
    data1 a;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a.x[i]);
    }
    sort(a.x, a.x + n);
    llong ret = 0;
    for (int i = 0, j = 1; i < n; ++i) {
        while (j < n && a.x[j] - a.x[i] <= d) ++j;
        ret += j - i;
    }
    return ret - n;
}

llong solve2() {
    data2 a;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &a.x[i], &a.y[i]);
        a.ps[i] = pii(a.x[i] + a.y[i] - 1, a.x[i] - a.y[i] + m);
    }
    sort(a.ps, a.ps + n);
    a.mx = (m << 1) - 1;
    llong ret = 0;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && a.ps[j].first - a.ps[i].first <= d)
            a.update(a.ps[j++].second, 1);
        a.update(a.ps[i].second, -1);
        ret += a.query(min(a.ps[i].second + d, a.mx));
        ret -= a.query(max(a.ps[i].second - d - 1, 0));
    }
    return ret;
}

llong solve3() {
    data3 a;
    a.mx = m;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d%d", &a.x[i], &a.y[i], &a.z[i]);
        a.ps[i] = data3::point(a.x[i], a.y[i], a.z[i]);
    }
    sort(a.ps, a.ps + n);
    a.mx = 3 * m - 2;
    llong ret = 0;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && a.ps[j].w - a.ps[i].w <= d) 
            a.update(a.ps[j].x, a.ps[j].y, a.ps[j].z, 1), ++j;
        a.update(a.ps[i].x, a.ps[i].y, a.ps[i].z, -1);
        int x = a.ps[i].x;
        int y = a.ps[i].y;
        int z = a.ps[i].z;
        
        for (int i = 0; i <= 1; ++i) {
            int qx = x + (2 * i - 1) * d + (i - 1);
            for (int j = 0; j <= 1; ++j) {
                int qy = y + (2 * j - 1) * d + (j - 1);
                for (int k = 0; k <= 1; ++k) {
                    int qz = z + (k * 2 - 1) * d + (k - 1);
                    ret += ((((i ^ j ^ k) & 1) << 1) - 1)
                        * a.query(a.in(qx), a.in(qy), a.in(qz));
                }
            }
        }
    }
    return ret;
}

int main() {
    int b;
    scanf("%d%d%d%d", &b, &n, &d, &m);
    llong ans;
    if (b == 1) ans = solve1();
    else if (b == 2) ans = solve2();
    else ans = solve3();
    printf("%lld\n", ans);
	return 0;
}

Compilation message

pairs.cpp: In function 'llong solve1()':
pairs.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a.x[i]);
         ~~~~~^~~~~~~~~~~~~~~
pairs.cpp: In function 'llong solve2()':
pairs.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a.x[i], &a.y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'llong solve3()':
pairs.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a.x[i], &a.y[i], &a.z[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:178:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &b, &n, &d, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 980 KB Output is correct
2 Correct 20 ms 980 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1840 KB Output is correct
2 Correct 3 ms 1840 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2696 KB Output is correct
2 Correct 33 ms 2696 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2736 KB Output is correct
2 Correct 39 ms 2736 KB Output is correct
3 Correct 40 ms 2736 KB Output is correct
4 Correct 38 ms 2796 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2796 KB Output is correct
2 Correct 48 ms 2796 KB Output is correct
3 Correct 44 ms 2796 KB Output is correct
4 Correct 45 ms 2796 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 44540 KB Output is correct
2 Correct 34 ms 44668 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 47356 KB Output is correct
2 Correct 95 ms 47356 KB Output is correct
3 Correct 83 ms 47356 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 47356 KB Output is correct
2 Correct 237 ms 47356 KB Output is correct
3 Correct 130 ms 47356 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 47356 KB Output is correct
2 Correct 317 ms 47464 KB Output is correct
3 Correct 204 ms 47464 KB Output is correct