oj.uz

Submission #485198

# Submission time Handle Problem Language Result Execution time Memory
485198 2021-11-06T14:20:53 Z Alexandruabcde Pairs (IOI07_pairs) C++14
100 / 100
 141 ms 9268 KB 
#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int MMAX2 = 75002;
constexpr int MMAX3 = 77;

typedef long long LL;

int Modul (int x) {
    if (x < 0) x = -x;

    return x;
}

int N, D, M;

void Task_1 () {
    cin >> N >> D >> M;
    vector <int> V(N);

    for (int i = 0; i < N; ++ i )
        cin >> V[i];

    sort(V.begin(), V.end());
    int left = 0;

    LL ans = 0;

    for (int i = 0; i < N; ++ i ) {
        while (left < i && V[left] < V[i] - D) ++ left;

        ans += 1LL * (i - left);
    }

    cout << ans << '\n';
}

int aib[2*MMAX2];

void Update (int pos, int val) {
    for (int i = pos; i <= 2 * M; i += ub(i))
        aib[i] += val;
}

int Query (int pos) {
    int S = 0;

    for (int i = pos; i; i -= ub(i))
        S += aib[i];

    return S;
}

void Task_2 () {
    cin >> N >> D >> M;
    vector <pair <int, int> > V(N);

    for (int i = 0; i < N; ++ i ) {
        int x, y;
        cin >> x >> y;
        V[i].first = x + y;
        V[i].second = x - y;
    }

    sort(V.begin(), V.end());

    int left = 0;
    LL ans = 0;
    for (int i = 0; i < N; ++ i ) {
        Update(V[i].second + M, 1);

        while (left < i && V[left].first < V[i].first - D) {
            Update(V[left].second + M, -1);
            ++ left;
        }

        ans += 1LL * (Query(min(2*M, V[i].second + M + D)) - Query(max(0, V[i].second + M - D - 1)) - 1);
    }

    cout << ans << '\n';
}

struct tridimensional {
    int x, y, z;
};

int mat[MMAX3][2*MMAX3][2*MMAX3];

void Task_3() {
    cin >> N >> D >> M;
    vector <tridimensional> V(N);

    for (int i = 0; i < N; ++ i ) {
        int x, y, z;
        cin >> x >> y >> z;

        V[i] = {x, y - z + M, y + z};

        mat[V[i].x][V[i].y][V[i].z] ++;
    }

    for (int i = 1; i <= M; ++ i ) {
        for (int j = 0; j <= 2*M; ++ j ) {
            for (int k = 0; k <= 2*M; ++ k ) {
                if (j > 0) mat[i][j][k] += mat[i][j-1][k];

                if (k > 0) mat[i][j][k] += mat[i][j][k-1];

                if (j > 0 && k > 0) mat[i][j][k] -= mat[i][j-1][k-1];
            }
        }
    }

    LL ans = 0;
    for (int i = 0; i < N; ++ i ) {
        for (int X = 1; X <= M; ++ X ) {
            int dist_left = D - Modul(X - V[i].x);

            if (dist_left < 0) continue;

            int X_st = max(0, V[i].y - dist_left - 1), Y_st = max(0, V[i].z - dist_left - 1);
            int X_dr = min(2*M, V[i].y + dist_left), Y_dr = min(2*M, V[i].z + dist_left);
            ans += 1LL * (mat[X][X_dr][Y_dr] - mat[X][X_st][Y_dr] - mat[X][X_dr][Y_st] + mat[X][X_st][Y_st]);
        }

        -- ans;
    }

    cout << ans / 2 << '\n';
}

void Solve (int B) {
    if (B == 1) {
        Task_1();
        return;
    }

    if (B == 2) {
        Task_2();
        return;
    }

    if (B == 3) {
        Task_3();
        return;
    }
}

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

    int B;
    cin >> B;

    Solve(B);
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 716 KB Output is correct
2 Correct 11 ms 716 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 716 KB Output is correct
2 Correct 15 ms 716 KB Output is correct

Subtask #5
6.0 / 6.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

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

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1100 KB Output is correct
2 Correct 26 ms 1108 KB Output is correct
3 Correct 24 ms 1124 KB Output is correct
4 Correct 26 ms 1116 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1632 KB Output is correct
2 Correct 30 ms 1624 KB Output is correct
3 Correct 30 ms 1604 KB Output is correct
4 Correct 28 ms 1632 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7244 KB Output is correct
2 Correct 9 ms 7224 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1612 KB Output is correct
2 Correct 20 ms 1612 KB Output is correct
3 Correct 23 ms 1660 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6064 KB Output is correct
2 Correct 79 ms 6948 KB Output is correct
3 Correct 68 ms 6852 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 8408 KB Output is correct
2 Correct 135 ms 9212 KB Output is correct
3 Correct 69 ms 9268 KB Output is correct