제출 #836936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836936		chanhchuong123	Pairs (IOI07_pairs)	C++14	100 / 100	434 ms	293964 KiB

pairs

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100010;
int type, N, D, M;

namespace taskOne {
    vector<int> p;

    struct BIT {
        vector<int> bit;
        int nE;

        BIT(int _n = 0) {
            nE = _n;
            bit.assign(_n + 5, 0);
        }

        void update(int id, int delta) {
            for (; id <= nE; id += id & -id)
                bit[id] += delta;
        }

        int get(int id) {
            if (id <= 0) return 0;
            int res = 0;
            for (; id > 0; id -= id & -id)
                res += bit[id];
            return res;
        }
    } bit;

    void solve(void) {
        cin >> N >> D >> M;
        for (int i = 1; i <= N; ++i) {
            int x; cin >> x;
            p.emplace_back(x);
        }
        BIT bit(M);
        long long ans = 0;
        sort(p.begin(), p.end());
        for (int i = 0; i < N; ++i) {
            int x = p[i];
            ans += i - bit.get(x - D - 1); bit.update(x, +1);
        }
        cout << ans;
    }
}

namespace taskTwo {
    vector<pair<int, int>> p;

    struct BIT {
        vector<int> bit;
        int nE, ADD;

        BIT(int _n = 0) {
            ADD = _n; nE = 4 * _n;
            bit.assign(nE + 5, 0);
        }

        void update(int id, int delta) {
            for (id += ADD; id <= nE; id += id & -id)
                bit[id] += delta;
        }

        int get(int id) {
            id += ADD;
            int res = 0;
            id = min(id, nE);
            for (; id > 0; id -= id & -id)
                res += bit[id];
            return res;
        }

        int get(int l, int r) {
            return get(r) - get(l - 1);
        }
    };

    void solve(void) {
        cin >> N >> D >> M;
        for (int i = 1; i <= N; ++i) {
            int x, y; cin >> x >> y;
            p.emplace_back(x + y, x - y);
        }
        BIT bit(M);
        long long ans = 0;
        sort(p.begin(), p.end());
        for (int i = 0, j = 0; i < N; ++i) {
            while (p[i].first - p[j].first > D) {
                bit.update(p[j].second, -1);
                ++j;
            }
            ans += bit.get(p[i].second - D, p[i].second + D);
            bit.update(p[i].second, +1);
        }
        cout << ans;
    }
}

namespace Miku_Nakano {
    struct point {
        int a, b, c, d;

        point(int x = 0, int y = 0, int z = 0, int t = 0) {
            a = x;
            b = y;
            c = z;
            d = t;
        }

        bool operator< (const point &other) const {
            if (a != other.a) return a < other.a;
            if (b != other.b) return b < other.b;
            if (c != other.c) return c < other.c;
            return d < other.d;
        }
    };
    vector<point> p;

    struct BIT {
        vector<vector<vector<int>>> bit;
        int nE; int ADD;

        BIT(int _n = 0) {
            nE = 5 * _n;
            ADD = 2 * _n;
            bit.resize(nE + 5);
            for (int i = 0; i <= nE; ++i) {
                bit[i].resize(nE + 5);
                for (int j = 0; j <= nE; ++j) {
                    bit[i][j].assign(nE + 5, 0);
                }
            }
        }

        void update(int x, int y, int z, int delta) {
            for (int i = x + ADD; i <= nE; i += i & -i) {
                for (int j = y + ADD; j <= nE; j += j & -j) {
                    for (int k = z + ADD; k <= nE; k += k & -k)
                        bit[i][j][k] += delta;
                }
            }
        }

        int get(int x, int y, int z) {
            x += ADD;
            y += ADD;
            z += ADD;
            x = min(x, nE);
            y = min(y, nE);
            z = min(z, nE);
            int res = 0;
            for (int i = x; i > 0; i -= i & -i) {
                for (int j = y; j > 0; j -= j & -j) {
                    for (int k = z; k > 0; k -= k & -k)
                        res += bit[i][j][k];
                }
            }
            return res;
        }

        int get(int x, int y, int z, int u, int v, int t) {
            return get(u, v, t)
                 - get(x - 1, v, t)
                 - get(u, y - 1, t)
                 - get(u, v, z - 1)
                 + get(x - 1, y - 1, t)
                 + get(x - 1, v, z - 1)
                 + get(u, y - 1, z - 1)
                 - get(x - 1, y - 1, z - 1);
        }
    };

    void solve(void) {
        cin >> N >> D >> M;
        for (int i = 1; i <= N; ++i) {
            int x, y, z; cin >> x >> y >> z;
            p.emplace_back(x + y + z, x - y + z, x + y - z, x - y - z);
        }
        BIT bit(M);
        long long ans = 0;
        sort(p.begin(), p.end());
        for (int i = 0, j = 0; i < N; ++i) {
            while (p[i].a - p[j].a > D) {
                bit.update(p[j].b, p[j].c, p[j].d, -1);
                ++j;
            }
            ans += bit.get(p[i].b - D, p[i].c - D, p[i].d - D,
                           p[i].b + D, p[i].c + D, p[i].d + D);
            bit.update(p[i].b, p[i].c, p[i].d, +1);
        }
        cout << ans;
    }
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	cin >> type;
	if (type == 1) taskOne::solve(); else
    if (type == 2) taskTwo::solve(); else
    Miku_Nakano::solve();

	return 0;
}

• 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