oj.uz

Submission #162877

# Submission time Handle Problem Language Result Execution time Memory
162877 2019-11-10T07:25:57 Z dolphingarlic Pairs (IOI07_pairs) C++14
100 / 100
 706 ms 44412 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int B, D, n, m;

int A[100002];
long long int ans;

// Literally just std::lower_bound

void solutionA() {
    for (int i = 1; i <= n; i++) cin >> A[i];
    sort(A + 1, A + n + 1);

    int fin = 1;
    for (int i = 1; i <= n; i++) {
        while (A[fin] - A[i] <= D && fin <= n) fin++;
        fin--;
        ans += (ll)(fin) - (ll)(i);
    }
    cout << ans << "\n";
}

int p, lim = 150002;
struct pt {
    pt(int _x, int _y, int _t) {
        x = _x;
        y = _y;
        t = _t;
    }
    int x, y;
    int t;
};
bool operator<(pt a, pt b) {
    if (a.x < b.x) return true;
    if (b.x < a.x) return false;
    if (a.y < b.y) return true;
    if (b.y < a.y) return false;
    return a.t == 0;
}
vector<pt> P;
int BIT[200002];

void get_coor(pt &a) {
    int x = a.x, y = a.y;
    a.x = x + y - 1;
    a.y = m - x + y;
}

void update(int x) {
    for (; x <= lim; x += (x & -x)) BIT[x]++;
}

int query(int x) {
    if (x == 0) return 0;
    int ret = 0;
    for (; x; x -= (x & -x)) ret += BIT[x];
    return ret;
}

// Line sweep + rotation + BIT

void solutionB() {
    for (int i = 1; i <= n; i++) {
        cin >> P[i].x >> P[i].y;
        P[i].t = 0;
        get_coor(P[i]);
    }

    p = n;
    lim = 2 * m - 1;
    for (int i = 1; i <= n; i++) {
        int nx = min(P[i].x + D, lim), ny = min(P[i].y + D, lim);
        P[++p] = pt(P[i].x - D - 1, P[i].y - D - 1, 1);
        P[++p] = pt(nx, ny, 1);
        P[++p] = pt(nx, P[i].y - D - 1, -1);
        P[++p] = pt(P[i].x - D - 1, ny, -1);
    }
    sort(P.begin() + 1, P.begin() + p + 1);

    long long int ans = 0;
    for (int i = 1; i <= p; i++) {
        if (P[i].x < 1 || P[i].y < 1) continue;
        if (P[i].t)
            ans += query(P[i].y) * P[i].t;
        else
            update(P[i].y);
    }
    ans -= n;
    ans /= 2;
    cout << ans << "\n";
}

struct pnt {
    int x, y, z;
};
pnt C[100002];
long long int M[202][202][202];

long long int sum(int k, int x, int y, int x1, int y1) {
    return M[k][x1][y1] - M[k][x1][y - 1] - M[k][x - 1][y1] +
           M[k][x - 1][y - 1];
}

void getNewCoor(pnt &a) {
    int x = a.x, y = a.y, z = a.z;
    a.x = x;
    a.y = y + z - 1;
    a.z = m - y + z;
}

// Rotate (x, y, z) -> (y + z - x, x + z - y, x + y - z) and prefix sums

void solutionC() {
    for (int i = 1; i <= n; i++) {
        cin >> C[i].x >> C[i].y >> C[i].z;
        getNewCoor(C[i]);
        M[C[i].x][C[i].y][C[i].z]++;
    }

    m *= 2;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= m; k++)
                M[i][j][k] +=
                    M[i][j][k - 1] + M[i][j - 1][k] - M[i][j - 1][k - 1];

    long long int ans = 0;
    int h, nx, ny, nx1, ny1;
    for (int x = 1; x <= n; x++)
        for (int i = 1; i <= m; i++) {
            h = D - abs(C[x].x - i);
            if (h >= 0) {
                nx = max(1, C[x].y - h);
                ny = max(1, C[x].z - h);
                nx1 = min(m, C[x].y + h);
                ny1 = min(m, C[x].z + h);
                ans += sum(i, nx, ny, nx1, ny1);
            }
        }

    ans -= n;
    ans /= 2;
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> B >> n >> D >> m;
    P = vector<pt>(500002, pt(0, 0, 0));
    if (B == 1)
        solutionA();
    else if (B == 2)
        solutionB();
    else
        solutionC();
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6392 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7072 KB Output is correct
2 Correct 24 ms 7080 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7416 KB Output is correct
2 Correct 29 ms 7544 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7420 KB Output is correct
2 Correct 30 ms 7548 KB Output is correct
3 Correct 29 ms 7544 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6776 KB Output is correct
2 Correct 9 ms 6780 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 6956 KB Output is correct
2 Correct 85 ms 6804 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 7032 KB Output is correct
2 Correct 104 ms 7160 KB Output is correct
3 Correct 101 ms 7072 KB Output is correct
4 Correct 99 ms 7052 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7980 KB Output is correct
2 Correct 104 ms 7956 KB Output is correct
3 Correct 103 ms 8004 KB Output is correct
4 Correct 108 ms 7952 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 42328 KB Output is correct
2 Correct 56 ms 42360 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8696 KB Output is correct
2 Correct 45 ms 8740 KB Output is correct
3 Correct 45 ms 8700 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 31452 KB Output is correct
2 Correct 319 ms 31480 KB Output is correct
3 Correct 209 ms 31504 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 44412 KB Output is correct
2 Correct 706 ms 44388 KB Output is correct
3 Correct 432 ms 44408 KB Output is correct