oj.uz

Submission #502938

# Submission time Handle Problem Language Result Execution time Memory
502938 2022-01-06T18:59:10 Z tabr Pairs (IOI07_pairs) C++17
100 / 100
 188 ms 2748 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

template <typename T>
struct fenwick {
    int n;
    vector<T> node;

    fenwick(int _n) : n(_n) {
        node.resize(n);
    }

    void add(int x, T v) {
        while (x < n) {
            node[x] += v;
            x |= (x + 1);
        }
    }

    T get(int x) {  // [0, x]
        T v = 0;
        while (x >= 0) {
            v += node[x];
            x = (x & (x + 1)) - 1;
        }
        return v;
    }

    T get(int x, int y) {  // [x, y]
        return (get(y) - (x ? get(x - 1) : 0));
    }

    int lower_bound(T v) {
        int x = 0;
        int h = 1;
        while (n >= (h << 1)) {
            h <<= 1;
        }
        for (int k = h; k > 0; k >>= 1) {
            if (x + k <= n && node[x + k - 1] < v) {
                v -= node[x + k - 1];
                x += k;
            }
        }
        return x;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int b, n, d, m;
    cin >> b >> n >> d >> m;
    if (b == 1) {
        vector<int> x(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }
        long long ans = 0;
        sort(x.begin(), x.end());
        for (int i = 0; i < n; i++) {
            ans += (int) (upper_bound(x.begin(), x.end(), x[i] + d) - x.begin() - i - 1);
        }
        cout << ans << '\n';
    } else if (b == 2) {
        vector<pair<int, int>> p(n);
        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            p[i] = make_pair(x - y, x + y);
        }
        sort(p.begin(), p.end());
        fenwick<int> f(m * 2 + 10);
        long long ans = 0;
        for (int beg = 0, end = 0; beg < n; beg++) {
            while (end < n && p[beg].first + d >= p[end].first) {
                f.add(p[end].second, 1);
                end++;
            }
            f.add(p[beg].second, -1);
            ans += f.get(max(0, p[beg].second - d), min(m * 2 + 9, p[beg].second + d));
        }
        cout << ans << '\n';
    } else {
        vector<vector<pair<int, int>>> a(m + 2);
        for (int i = 0; i < n; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            a[z].emplace_back(x - y, x + y);
        }
        for (int i = 0; i < m + 2; i++) {
            sort(a[i].begin(), a[i].end());
        }
        long long ans = 0;
        for (int i = 0; i < m + 2; i++) {
            for (int j = i + 1; j < m + 2; j++) {
                int c = d - j + i;
                if (c < 0) {
                    break;
                }
                fenwick<int> f(m * 2 + 10);
                for (int k = 0, beg = 0, end = 0; k < (int) a[i].size(); k++) {
                    while (end < (int) a[j].size() && a[i][k].first + c >= a[j][end].first) {
                        f.add(a[j][end].second, 1);
                        end++;
                    }
                    while (beg < end && a[i][k].first - c > a[j][beg].first) {
                        f.add(a[j][beg].second, -1);
                        beg++;
                    }
                    ans += f.get(max(0, a[i][k].second - c), min(m * 2 + 9, a[i][k].second + c));
                }
            }
            fenwick<int> f(m * 2 + 10);
            for (int beg = 0, end = 0; beg < (int) a[i].size(); beg++) {
                while (end < (int) a[i].size() && a[i][beg].first + d >= a[i][end].first) {
                    f.add(a[i][end].second, 1);
                    end++;
                }
                f.add(a[i][beg].second, -1);
                ans += f.get(max(0, a[i][beg].second - d), min(m * 2 + 9, a[i][beg].second + d));
            }
        }
        cout << ans << '\n';
    }
    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 1 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 15 ms 1088 KB Output is correct
2 Correct 14 ms 1096 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1464 KB Output is correct
2 Correct 18 ms 1460 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1476 KB Output is correct
2 Correct 21 ms 1476 KB Output is correct
3 Correct 24 ms 1468 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1604 KB Output is correct
2 Correct 26 ms 1608 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1868 KB Output is correct
2 Correct 29 ms 1852 KB Output is correct
3 Correct 31 ms 1852 KB Output is correct
4 Correct 28 ms 1852 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2748 KB Output is correct
2 Correct 36 ms 2736 KB Output is correct
3 Correct 31 ms 2740 KB Output is correct
4 Correct 30 ms 2740 KB Output is correct

Subtask #10
10.0 / 10.0

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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2112 KB Output is correct
2 Correct 41 ms 2164 KB Output is correct
3 Correct 28 ms 2120 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2224 KB Output is correct
2 Correct 153 ms 2244 KB Output is correct
3 Correct 80 ms 2284 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 2520 KB Output is correct
2 Correct 188 ms 2488 KB Output is correct
3 Correct 109 ms 2500 KB Output is correct