Submission #613605

#	Time	Username	Problem	Language	Result	Execution time	Memory
613605		KoD	Segments (IZhO18_segments)	C++17	100 / 100	4753 ms	20644 KiB

segments

#pragma GCC target("avx2")
// #pragma GCC target("popcnt")
#include <bits/stdc++.h>

using u64 = std::uint64_t;
using std::vector;
using std::array;
using std::pair;
using std::tuple;

int popcount(const u64 x) {
    return __builtin_popcountll(x);
}

template <class T>
int lowb(const vector<T>& vec, const T& x) {
    return std::lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

class bit_vector {
    array<int, 2> all;
    vector<u64> block;
    vector<int> accum;

  public:
    bit_vector() = default;

    explicit bit_vector(const vector<int>& vec) {
        const int n = (int)vec.size();
        const int size = (n + 63) / 64;
        all.fill(0);
        block.resize(size + 1);
        for (int i = 0; i < n; ++i) {
            all[vec[i]] += 1;
            block[i / 64] |= (u64)vec[i] << (i & 63);
        }
        accum.resize(size + 1);
        for (int i = 0; i < size; ++i) {
            accum[i + 1] = accum[i] + popcount(block[i]);
        }
    }

    int count(const int x) const {
        return all[x];
    }

    int count(const int k, const int x) const {
        const u64 mask = ((u64)1 << (k & 63)) - 1;
        const int one = accum[k / 64] + popcount(block[k / 64] & mask);
        return x == 1 ? one : k - one;
    }

    int count(const int l, const int r, const int x) const {
        return count(r, x) - count(l, x);
    }
};

template <int Digit>
class wavelet_matrix {
    array<bit_vector, Digit> bit;

  public:
    wavelet_matrix() = default;

    explicit wavelet_matrix(const vector<int>& vec) {
        const int n = (int)vec.size();
        vector<int> build(n), idx(n), next(n);
        std::iota(idx.begin(), idx.end(), 0);
        for (int d = Digit - 1; d >= 0; --d) {
            auto zero = next.begin();
            auto one = next.rbegin();
            for (int i = 0; i < n; ++i) {
                build[i] = vec[idx[i]] >> d & 1;
                (build[i] ? *one++ : *zero++) = idx[i];
            }
            bit[d] = bit_vector(build);
            std::reverse(next.rbegin(), one);
            std::swap(idx, next);
        }
    }

    int count(int l, int r, const int x) const {
        int ret = 0;
        for (int d = Digit - 1; d >= 0; --d) {
            const int lc = bit[d].count(l, 1);
            const int rc = bit[d].count(r, 1);
            if (x >> d & 1) {
                l = bit[d].count(0) + lc;
                r = bit[d].count(0) + rc;
            } else {
                ret += (rc - lc);
                l -= lc;
                r -= rc;
            }
        }
        return ret + (r - l);
    }
};

class point_container {
    vector<int> xs, ys;
    wavelet_matrix<18> matrix;

  public:
    point_container() = default;

    explicit point_container(vector<pair<int, int>>&& vec) {
        xs.reserve(vec.size());
        ys.reserve(vec.size());
        std::sort(vec.begin(), vec.end());
        for (const auto& [x, y] : vec) {
            xs.push_back(x);
            ys.push_back(y);
        }
        std::sort(ys.begin(), ys.end());
        ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
        vector<int> build;
        build.reserve(vec.size());
        for (const auto& [x, y] : vec) {
            build.push_back(lowb(ys, y));
        }
        matrix = wavelet_matrix<18>(build);
    }

    int count(const int xl, const int xr, const int y) const {
        return matrix.count(lowb(xs, xl), lowb(xs, xr), lowb(ys, y));
    }
};

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

    int Q, T, Answer = 0;
    std::cin >> Q >> T;

    int N = 0, M = 0;
    vector<int> X(Q), Y(Q), list;
    vector<char> active(Q), focus(Q);
    point_container P1, P2;

    const auto build = [&] {
        M = N;
        vector<pair<int, int>> p1, p2;
        p1.reserve(M);
        p2.reserve(M);
        for (int i = 0; i < M; ++i) {
            if (active[i]) {
                p1.emplace_back(X[i], Y[i]);
                p2.emplace_back(X[i], Y[i] - X[i]);
            }
        }
        P1 = point_container(std::move(p1));
        P2 = point_container(std::move(p2));
        for (const int i : list) {
            focus[i] = false;
        }
        list.clear();
    };

    const auto add = [&](const int x, const int y) {
        X[N] = x;
        Y[N] = y;
        active[N] = true;
        focus[N] = true;
        list.push_back(N);
        N += 1;
    };

    const auto remove = [&](const int id) {
        if (!focus[id]) {
            focus[id] = true;
            list.push_back(id);
        }
        active[id] = false;
    };

    const auto solve = [&](const int l, const int r, const int k) {
        if (r - l < k) {
            return 0;
        }
        int ret = 0;
        if (M > 0) {
            ret += P1.count(0, l, l + k);
            ret += P2.count(l, r - k + 1, k);
        }
        for (const int id : list) {
            if (id < M) {
                if (!active[id] and ((X[id] <= l and Y[id] >= l + k) or (l <= X[id] and X[id] <= r - k and Y[id] >= X[id] + k))) {
                    ret -= 1;
                }
            } else {
                if (active[id] and ((X[id] <= l and Y[id] >= l + k) or (l <= X[id] and X[id] <= r - k and Y[id] >= X[id] + k))) {
                    ret += 1;
                }
            }
        }
        return ret;
    };

    for (int q = 0; q < Q; ++q) {
        if ((int)list.size() > 3500) {
            build();
        }
        int t;
        std::cin >> t;
        if (t == 1) {
            int a, b;
            std::cin >> a >> b;
            if (T == 1) {
                a ^= Answer;
                b ^= Answer;
            }
            if (a > b) {
                std::swap(a, b);
            }
            add(a, b);
        } else if (t == 2) {
            int id;
            std::cin >> id;
            remove(id - 1);
        } else {
            int a, b, k;
            std::cin >> a >> b >> k;
            if (T == 1) {
                a ^= Answer;
                b ^= Answer;
            }
            if (a > b) {
                std::swap(a, b);
            }
            Answer = solve(a, b, k - 1);
            std::cout << Answer << '\n';
        }
    }
    return 0;
}

/*
6 1
1 1 2
3 2 4 2
1 3 5
3 2 3 1
2 1
3 0 3 1

6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2
*/

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 25 / 25