Submission #54599

#	Time	Username	Problem	Language	Result	Execution time	Memory
54599		imeimi2000	Pairs (IOI07_pairs)	C++17	100 / 100	347 ms	47464 KiB

pairs

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

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 / 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