Submission #226393

#	Time	Username	Problem	Language	Result	Execution time	Memory
226393		covfefe	Weighting stones (IZhO11_stones)	C++17	0 / 100	5 ms	384 KiB

stones

#include <iostream>
#include <vector>
#include <algorithm>
#include <optional>


template<typename T, typename FuncFunctor, typename ConcatFunctor>
class SegmentTree {
private:
    std::vector<T> array;
    size_t sz;
    FuncFunctor func;
    ConcatFunctor concat;

    inline size_t leftChild(size_t i) {
        return 2 * i + 1;
    }

    inline size_t rightChild(size_t i) {
        return 2 * i + 2;
    }

    bool intersect(const size_t &l1, const size_t &r1, const size_t &l2, const size_t &r2) {
        return std::max(l1, l2) < std::min(r1, r2);
    }

    size_t closestPowerOf2(size_t n) {
        if (n == 1)
            return 1;

        else {
            return 2 * closestPowerOf2(n / 2);
        }
    }

    T RecursiveFillValue(size_t l, size_t r, size_t i, const T &value) {
        if (l + 1 == r) {
            array[i] = value;
            return func(array[i]);
        } else {
            T leftValue = RecursiveFillValue(l, 1 + (l + r - 1) / 2, leftChild(i), value);
            T rightValue = RecursiveFillValue(1 + (l + r - 1) / 2, r, rightChild(i), value);
            array[i] = concat(leftValue, rightValue);
            return array[i];
        }
    }

    T RecursiveFillArray(size_t l, size_t r, size_t i, T *arr) {
        if (l + 1 == r) {
            array[i] = arr[l];
            return func(array[i]);
        } else {
            T leftValue = RecursiveFillArray(l, 1 + (l + r - 1) / 2, leftChild(i), arr);
            T rightValue = RecursiveFillArray(1 + (l + r - 1) / 2, r, rightChild(i), arr);
            array[i] = concat(leftValue, rightValue);
            return array[i];
        }
    }

    T Query(size_t l, size_t r, size_t lcur, size_t rcur, size_t i) {
        if (l <= lcur && rcur <= r) {
            if (lcur + 1 == rcur) { // if we're in a leaf
                return func(array[i]); // Calculate function value
            }

            return array[i]; // Otherwise return node value
        } else {
            size_t midpoint = 1 + (lcur + rcur - 1) / 2;
            bool left = intersect(l, r, lcur, midpoint);
            bool right = intersect(l, r, midpoint, rcur);
            if (left && right) {
                return concat(Query(l, r, lcur, midpoint, leftChild(i)), Query(l, r, midpoint, rcur, rightChild(i)));
            } else if (left) {
                return Query(l, r, lcur, midpoint, leftChild(i));
            } else {
                return Query(l, r, midpoint, rcur, rightChild(i));
            }
        }
    }

    T Set(size_t index, const T &newValue, size_t l, size_t r, size_t i) {
        if (l + 1 == r) {
            array[i] = newValue;
            return func(array[i]);
        } else {
            size_t midpoint = 1 + (l + r - 1) / 2;
            if (index < midpoint) {
                array[i] = concat(Set(index, newValue, l, midpoint, leftChild(i)),
                                  ((midpoint + 1 == r) ? func(array[rightChild(i)]) : array[rightChild(i)]));
            } else {
                array[i] = concat(((l + 1 == midpoint) ? func(array[leftChild(i)]) : array[leftChild(i)]),
                                  Set(index, newValue, midpoint, r, rightChild(i)));
            }
            return array[i];
        }
    }

    std::optional<size_t> KthEntryIndex(size_t k, size_t l, size_t r, size_t i) {
        if (l + 1 == r) { // If we are in a leaf, return index
            if (k == 1 && func(array[i])) // If we are looking for the first element and leaf satisfies the property
                return std::make_optional(l); // Return its index
            else
                return std::nullopt; // No result
        } else {
            size_t midpoint = 1 + (l + r - 1) / 2; // Middle of an line
            if (l + 1 == midpoint) { // If there is a leaf on the left
                if (k == 1 && func(array[leftChild(
                        i)])) { // If we are looking for the first encounter AND there left child satisfies
                    return KthEntryIndex(k, l, midpoint, leftChild(i)); // Go to this leaf
                } else {
                    return KthEntryIndex(k - (func(array[leftChild(i)]) ? 1 : 0), midpoint, r,
                                         rightChild(i)); // Otherwise to right subtree
                }
            } else {
                if (k <= array[leftChild(i)]) { // Otherwise if there is enough encounters in the left subtree
                    return KthEntryIndex(k, l, midpoint, leftChild(i)); // Go to left subtree
                } else {
                    return KthEntryIndex(k - array[leftChild(i)], midpoint, r,
                                         rightChild(i)); // Otherwise proceed to the right
                }
            }
        }
    }

public:
    T Query(size_t l, size_t r) {
        return Query(l, r, 0, sz, 0);
    }

    void Set(size_t index, const T &newValue) {
        Set(index, newValue, 0, sz, 0);
    }

    size_t size() {
        return sz;
    }

    std::optional<size_t> KthEntryIndex(size_t k, size_t l,
                                        size_t r) { // If function is filter and concat is sum, we can find Kth entry of element with property func(x) = 1
        size_t offset = (l == 0) ? 0 : Query(0, l);
        size_t offset2 = (l == 0) ? 0 : Query(r, sz);
        size_t total = Query(0, sz);

        if (total - (offset + offset2) >= k) {
            auto answer = KthEntryIndex(k + offset, 0, sz, 0);
            if (answer && (*answer < r))
                return answer;

            return std::nullopt;
        } else {
            return std::nullopt;
        }
    }

    SegmentTree(size_t size, const T &value = T()) : func(), concat() { // Default constructor
        sz = closestPowerOf2(size);
        if (sz < size) {
            sz *= 2;
        }
        sz *= 2;
        sz--;

        array = std::vector<T>(sz);

        sz = size;

        RecursiveFillValue(0, sz, 0, value); // Initialize structure with value
    }

    SegmentTree(size_t size, T *arr)
            : func(), concat() { // Array constructor. Array size must be greater or equal to sz parameter
        sz = closestPowerOf2(size);
        if (sz < size) {
            sz *= 2;
        }
        sz *= 2;
        sz--;

        array = std::vector<T>(sz);

        sz = size;

        RecursiveFillArray(0, sz, 0, arr); // Initialize structure with array values
    }
};

using namespace std;

struct weight_functor {
    pair<int, int> operator()(const pair<int, int> &a) {
        return a;
    }
};

struct weigth_concat_functor {
    pair<int, int> operator()(const pair<int, int> &a, const pair<int, int> &b) {
        return {min(b.first, a.first + b.first), max(b.second, a.second + b.second)};
    }
};

int main() {
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> firstRequests;
    vector<int> secondRequests;
    vector<int> sideNumber;

    SegmentTree<pair<int, int>, weight_functor, weigth_concat_functor> Stones(n);

    int order = 0;
    int side = 0;

    for (int i = 0; i < n; i++) {
        cin >> order >> side;
        order--;
        if(side == 1) {
            Stones.Set(order, {1, 1});
        } else {
            Stones.Set(order, {-1, -1});
        }
        pair<int, int> state = Stones.Query(0, n);
        bool positiveMax = state.second > 0;
        bool negativeMin = state.first < 0;
        if(positiveMax && negativeMin)
            cout << "?\n";
        else if(positiveMax)
            cout << ">\n";
        else
            cout << "<\n";
    }
}

• Subtask 1: 0 / 100