Submission #849507

#	Time	Username	Problem	Language	Result	Execution time	Memory
849507		popovicirobert	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	1442 ms	524288 KiB

street_lamps

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

namespace Containers {

    template<typename T>
    struct Segment {
        T l, r;
        bool operator<(const Segment& rhs) const noexcept {
            if (l == rhs.l) return r < rhs.r;
            return l < rhs.l;
        }
    };

    template<typename T>
    class DisjointSegmentContainer : public multiset<Segment<T>> {
    public:
        vector<Segment<T>> Add(Segment<T> segm) {
            auto intersecting = GetIntersecting(segm);

            T new_l = segm.l;
            T new_r = segm.r;

            for (auto s : intersecting) {
                new_l = min(new_l, s.l);
                new_r = max(new_r, s.r);
                this->erase(this->find(s));
            }

            this->insert({new_l, new_r});

            return intersecting;
        }

        vector<Segment<T>> GetIntersecting(Segment<T> segm) {
            vector<Segment<T>> intersecting;

            auto itr = this->insert(segm);
            if (itr != this->begin()) {
                auto prv = prev(itr);
                while (prv->r >= segm.l) {
                    intersecting.push_back(*prv);
                    if (prv == this->begin()) {
                        break;
                    }
                    prv = prev(prv);
                }
            }

            auto nxt = next(itr);
            while (nxt != this->end() && nxt->l <= segm.r) {
                intersecting.push_back(*nxt);
                nxt = next(nxt);
            }

            this->erase(itr);

            return intersecting;
        }

        void Remove(Segment<T> segm) {
            auto itr = this->find(segm);
            if (itr == this->end()) {
                assert(false);
            }
            this->erase(itr);
        }
    };
}

using SegmentContainer = Containers::DisjointSegmentContainer<int>;
using Segment = Containers::Segment<int>;

namespace Space2D {

    struct Update2D {
        int x1, x2;
        int y1, y2;

        Update2D(int x1, int x2, int y1, int y2) {
            this->x1 = x1;
            this->x2 = x2;
            this->y1 = y1;
            this->y2 = y2;
        }

        int value;
        int updateId;
    };

    struct Update1D {
        int x1, x2;

        Update1D(Update2D u) {
            this->x1 = u.x1;
            this->x2 = u.x2;
            this->value = u.value;
            this->updateId = u.updateId;
        }

        int value;
        int updateId;
    };
  
    struct NodeInfo {
        int value = -1;
        int updateId = -1;

        static NodeInfo merge(NodeInfo a, NodeInfo b) {
            return a.updateId > b.updateId ? a : b;
        }
    };

    class SegTree1D {
        struct Node {
            int idl = -1, idr = -1;
            NodeInfo lazy;
        };

    public:
        SegTree1D(int minX, int maxX) {
            this->minX = minX;
            this->maxX = maxX;
            makeNode();
        }

        inline int makeNode() {
            int id = (int)tree.size();
            tree.push_back({});
            return id;
        }

        void set(Update1D u) {
            set(0, minX, maxX, u);
        }

        NodeInfo query(int x) {
            return query(0, minX, maxX, x);
        }

    private:
        int set(int id, int x1, int x2, Update1D u) {
            if (id == -1) {
                id = makeNode();
            }

            if (u.x1 <= x1 && x2 <= u.x2) {
                tree[id].lazy = {u.value, u.updateId};
            } else {
                int mid = (x1 + x2) / 2;
                if (u.x1 <= mid) {
                    int idl = set(tree[id].idl, x1, mid, u);
                    tree[id].idl = idl;
                } 
                if (mid < u.x2) {
                    int idr = set(tree[id].idr, mid + 1, x2, u);
                    tree[id].idr = idr;
                }
            }

            return id;
        }

        NodeInfo query(int id, int x1, int x2, int x) {
            if (id == -1) {
                return {};
            }

            if (x1 == x2) {
                return tree[id].lazy;
            } else {
                int mid = (x1 + x2) / 2;
                if (x <= mid) {
                    auto info = query(tree[id].idl, x1, mid, x);
                    return NodeInfo::merge(info, tree[id].lazy);
                } else {
                    auto info = query(tree[id].idr, mid + 1, x2, x);
                    return NodeInfo::merge(info, tree[id].lazy);
                }
            }
        }

    private:
        vector<Node> tree;
        int minX, maxX;
    };

    class SegTree2D {
    struct Node {
        int idl, idr;
        SegTree1D tree;

        Node(int minY, int maxY) : tree(minY, maxY) {
            idl = idr = -1;
        }
    };

    public:
        SegTree2D(int minX, int maxX, int minY, int maxY) {
            this->minX = minX;
            this->maxX = maxX;
            this->minY = minY;
            this->maxY = maxY;
            makeNode();
        }

        inline int makeNode() {
            int id = (int)tree.size();
            tree.push_back(Node(minY, maxY));
            return id;
        }

        void set(Update2D u, int value) {
            static int updateId = 0;

            u.value = value;
            u.updateId = ++updateId;

            set(0, minX, maxX, u);
        }

        int query(int x, int y) {
            return query(0, minX, maxX, x, y).value;
        }

    private:
        int set(int id, int x1, int x2, Update2D u) {
            if (id == -1) {
                id = makeNode();
            }

            if (u.x1 <= x1 && x2 <= u.x2) {
                tree[id].tree.set(u);
            } else {
                int mid = (x1 + x2) / 2;
                if (u.x1 <= mid) {
                    int idl = set(tree[id].idl, x1, mid, u);
                    tree[id].idl = idl;
                }
                if (mid < u.x2) {
                    int idr = set(tree[id].idr, mid + 1, x2, u);
                    tree[id].idr = idr;
                }
            }

            return id;
        }

        NodeInfo query(int id, int x1, int x2, int x, int y) {
            if (id == -1) {
                return {-1, -1};
            }

            if (x1 == x2) {
                return tree[id].tree.query(y);
            } else {
                int mid = (x1 + x2) / 2;
                NodeInfo info;
                if (x <= mid) {
                    info = query(tree[id].idl, x1, mid, x, y);
                } else {
                    info = query(tree[id].idr, mid + 1, x2, x, y);
                }
                // auto temp = tree[id].tree.query(y);
                // cerr << x1 << " " << x2 << " " << temp.updateId << " " << temp.value << "\n";
                return NodeInfo::merge(info, tree[id].tree.query(y));
            }
        }

    private:
        vector<Node> tree;
        int minX, maxX;
        int minY, maxY;
    };
}

namespace std {
    template<>
    struct hash<pair<int, int>> {
        size_t operator()(const pair<int, int>& p) const noexcept {
            return (p.first << 16) ^ p.second;
        }
    };
}


namespace UniqueIndexGenerator {
    constexpr int SMALL_X = (int) 4e5;

    template<typename _Derived, typename T = typename _Derived::type>
    class BaseGenerator {
    public:
        inline int getIndex(T x, T y) const {
            return reinterpret_cast<const _Derived*>(this)->getIndex(x, y);
        }

        inline int getOrAddIndex(T x, T y) {
            return reinterpret_cast<_Derived*>(this)->getOrAddIndex(x, y);
        }

    protected:
        inline int nextID() const noexcept {
            static int ID = -1;
            return ++ID;
        }
    };

    template<typename T>
    class SmallXGenerator : public BaseGenerator<SmallXGenerator<T>, T> {
    public:
        using type = T;

        SmallXGenerator(int maxX, int maxY) {
            index.resize(maxX + 1);
        }

        inline int getIndex(int x, int y) const {
            auto itr = index[x].find(y);
            return itr == index[x].end() ? -1 : itr->second;
        }

        inline int getOrAddIndex(int x, int y) {
            auto itr = index[x].find(y);
            if (itr == index[x].end()) {
                int id = this->nextID();
                index[x].insert({y, id});
                return id;
            }
            return itr->second;
        }
    private:
        vector<unordered_map<T, int>> index;
    };

    template<typename T>
    class GeneralGenerator : public BaseGenerator<GeneralGenerator<T>, T> {
    public:
        using type = T;

        GeneralGenerator(T maxX, T maxY) {}

        inline int getIndex(T x, T y) const {
            auto itr = index.find({x, y});
            return itr == index.end() ? -1 : itr->second;
        }

        inline int getOrAddIndex(T x, T y) {
            auto itr = index.find({x, y});
            if (itr == index.end()) {
                int id = this->nextID();
                index.insert(make_pair(make_pair(x, y), id));
                return id;
            }
            return itr->second;
        }

    private:
        unordered_map<pair<T, T>, int> index;
    };
}


template<typename _TGenerator>
class Fenwick2D {
    using T = typename _TGenerator::type;

public:
    Fenwick2D(T maxX, T maxY, UniqueIndexGenerator::BaseGenerator<_TGenerator>& uniqueGenerator)
        : uniqueGenerator(uniqueGenerator) {

        this->maxX = maxX;
        this->maxY = maxY;
    }

    inline void reserve(int size) {
        data.resize(size + 1);
    }

    inline T getData(T x, T y) const {
        int id = uniqueGenerator.getIndex(x, y);
        return id == -1 ? 0 : data[id];
    }

    inline int getOrAddIndex(T x, T y) {
        int id = uniqueGenerator.getOrAddIndex(x, y);
        if ((int)data.size() <= id) {
            data.resize(id + 1);
        }
        return id;
    }

    T query(T qx, T qy) const {
        T answer = 0;
        for (T x = qx; x > 0; x -= lsb(x)) {
            for (T y = qy; y > 0; y -= lsb(y)) {
                answer += getData(x, y);
            }
        }
        return answer;
    }

    void update(T ux, T uy, T value) {
        for (T x = ux; x <= maxX; x += lsb(x)) {
            for (T y = uy; y <= maxY; y += lsb(y)) {
                data[getOrAddIndex(x, y)] += value;
            }
        }
    }

private:
    T maxX, maxY;
    UniqueIndexGenerator::BaseGenerator<_TGenerator>& uniqueGenerator;
    
    vector<T> data;
};

int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, q;
    cin >> n >> q;

    string str;
    cin >> str;
    str = " " + str; 

    vector<pair<ll, ll>> segments;
    {   
        int i = 1;
        while (i <= n) {
            if (str[i] == '0') {
                segments.push_back({i, i});
                i++;
            } else {
                int j = i;
                while (j <= n && str[j] == '1') {
                    j++;
                }
                segments.push_back({i, j});
                i = j + 1;
            }
        }
        if (segments.back().second != n + 1) {
            segments.push_back({n + 1, n + 1});
        }
    }

    SegmentContainer container;
    Space2D::SegTree2D st(1, n + 1, 1, n + 1);

    for (auto s : segments) {
        container.Add({s.first, s.second});
        st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
    }

    // cerr << st.query(1, 6);

    UniqueIndexGenerator::SmallXGenerator<int> generator(n + 1, n + 1);
    Fenwick2D<decltype(generator)> fen(n + 1, n + 1, generator);
    fen.reserve(q * 17 * 17);

    for (int qq = 1; qq <= q; qq++) {
        string t;
        cin >> t;

        if (t == "query") {
            int x, y;
            cin >> x >> y;

            int answer = fen.query(x, y);
            // cerr << answer << "\n";

            int lastId = st.query(x, y);
            if (lastId != -1) {
                answer += qq - lastId;
            }

            cout << answer << "\n";

        } else {
            int pos;
            cin >> pos;

            auto Remove = [&](Segment segm) {
                int lastId = st.query(segm.l, segm.r);
                assert(lastId != -1);
                int value = qq - lastId;

                // cerr << "Remove --> " << segm.l << " " << segm.r << " " << lastId << "\n";

                fen.update(segm.l, segm.l, value);
                fen.update(segm.r + 1, segm.l, -value);
                fen.update(segm.l, segm.r + 1, -value);
                fen.update(segm.r + 1, segm.r + 1, value);

                st.set({segm.l, segm.r, segm.l, segm.r}, -1);
                container.Remove(segm);
            };

            auto Add = [&](Segment segm) {
                st.set({segm.l, segm.r, segm.l, segm.r}, qq);

                // cerr << "Add --> " << segm.l << " " << segm.r << " " << qq << "\n";

                container.Add(segm);
            };
            
            if (str[pos] == '1') {
                auto intersecting = container.GetIntersecting({pos, pos});
                assert(intersecting.size() == 1);

                auto segm = intersecting[0];
                Remove(segm);
                Add({segm.l, pos});
                Add({pos + 1, segm.r});
            } else {
                auto intersecting = container.GetIntersecting({pos, pos + 1});
                assert(intersecting.size() == 2);

                auto segm1 = intersecting[0];
                auto segm2 = intersecting[1];
                Remove(segm1);
                Remove(segm2);
                Add({segm1.l, segm2.r});
            }
            str[pos] = (str[pos] == '0' ? '1' : '0');
        }
    }

    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:463:26: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
  463 |         container.Add({s.first, s.second});
      |                        ~~^~~~~
street_lamps.cpp:463:35: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
  463 |         container.Add({s.first, s.second});
      |                                 ~~^~~~~~
street_lamps.cpp:464:36: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
  464 |         st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
      |                                  ~~^~~~~
street_lamps.cpp:464:45: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
  464 |         st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
      |                                           ~~^~~~~~
street_lamps.cpp:464:55: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
  464 |         st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
      |                                                     ~~^~~~~
street_lamps.cpp:464:64: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
  464 |         st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
      |                                                              ~~^~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20