Submission #485198

#	Time	Username	Problem	Language	Result	Execution time	Memory
485198		Alexandruabcde	Pairs (IOI07_pairs)	C++14	100 / 100	141 ms	9268 KiB

pairs

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