Submission #502938

#	Time	Username	Problem	Language	Result	Execution time	Memory
502938		tabr	Pairs (IOI07_pairs)	C++17	100 / 100	188 ms	2748 KiB

pairs

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