oj.uz

답안 #836936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836936 2023-08-24T17:27:14 Z chanhchuong123 Pairs (IOI07_pairs) C++14
100 / 100
 434 ms 293964 KB 
#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.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 293964 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1356 KB Output is correct
2 Correct 12 ms 1240 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 275660 KB Output is correct
2 Correct 132 ms 275656 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 275656 KB Output is correct
2 Correct 134 ms 275644 KB Output is correct
3 Correct 135 ms 275660 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2004 KB Output is correct
2 Correct 19 ms 2128 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 2260 KB Output is correct
2 Correct 24 ms 2132 KB Output is correct
3 Correct 23 ms 2132 KB Output is correct
4 Correct 22 ms 2132 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 3408 KB Output is correct
2 Correct 27 ms 3408 KB Output is correct
3 Correct 27 ms 3408 KB Output is correct
4 Correct 26 ms 3412 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 216148 KB Output is correct
2 Correct 111 ms 216148 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 3160 KB Output is correct
2 Correct 40 ms 3168 KB Output is correct
3 Correct 35 ms 3276 KB Output is correct

Subtask #12
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 113988 KB Output is correct
2 Correct 291 ms 114228 KB Output is correct
3 Correct 146 ms 114048 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 218576 KB Output is correct
2 Correct 434 ms 218572 KB Output is correct
3 Correct 278 ms 218572 KB Output is correct