Submission #849154

#	Time	Username	Problem	Language	Result	Execution time	Memory
849154		popovicirobert	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	5116 ms	440416 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 {

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

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

            ll new_l = segm.l;
            ll 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> GetIntersecting(Segment segm) {
            vector<Segment> 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 segm) {
            auto itr = this->find(segm);
            if (itr == this->end()) {
                assert(false);
            }
            this->erase(itr);
        }
    };
}

using SegmentContainer = Containers::DisjointSegmentContainer;

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;
        }
    };
}

class Fenwick2D {
public:
    Fenwick2D(int maxX, int maxY) {
        this->maxX = maxX;
        this->maxY = maxY;
    }

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

    inline int getIndex(int x, int y) {
        auto itr = index.find({x, y});
        if (itr == index.end()) {
            int id = (int)data.size();
            data.push_back(0);
            index.insert(make_pair(make_pair(x, y), id));
            return id;
        }
        return itr->second;
    }

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

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

private:
    int maxX, maxY;

    unordered_map<pair<int, int>, int> index;
    vector<int> 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);

    Fenwick2D fen(n + 1, n + 1);

    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 = [&](Containers::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 = [&](Containers::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:378:36: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
  378 |         st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
      |                                  ~~^~~~~
street_lamps.cpp:378:45: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
  378 |         st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
      |                                           ~~^~~~~~
street_lamps.cpp:378:55: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
  378 |         st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
      |                                                     ~~^~~~~
street_lamps.cpp:378:64: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
  378 |         st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
      |                                                              ~~^~~~~~
street_lamps.cpp: In lambda function:
street_lamps.cpp:419:30: warning: narrowing conversion of 'segm.Containers::Segment::l' from 'long long int' to 'int' [-Wnarrowing]
  419 |                 st.set({segm.l, segm.r, segm.l, segm.r}, -1);
      |                         ~~~~~^
street_lamps.cpp:419:38: warning: narrowing conversion of 'segm.Containers::Segment::r' from 'long long int' to 'int' [-Wnarrowing]
  419 |                 st.set({segm.l, segm.r, segm.l, segm.r}, -1);
      |                                 ~~~~~^
street_lamps.cpp:419:46: warning: narrowing conversion of 'segm.Containers::Segment::l' from 'long long int' to 'int' [-Wnarrowing]
  419 |                 st.set({segm.l, segm.r, segm.l, segm.r}, -1);
      |                                         ~~~~~^
street_lamps.cpp:419:54: warning: narrowing conversion of 'segm.Containers::Segment::r' from 'long long int' to 'int' [-Wnarrowing]
  419 |                 st.set({segm.l, segm.r, segm.l, segm.r}, -1);
      |                                                 ~~~~~^
street_lamps.cpp: In lambda function:
street_lamps.cpp:424:30: warning: narrowing conversion of 'segm.Containers::Segment::l' from 'long long int' to 'int' [-Wnarrowing]
  424 |                 st.set({segm.l, segm.r, segm.l, segm.r}, qq);
      |                         ~~~~~^
street_lamps.cpp:424:38: warning: narrowing conversion of 'segm.Containers::Segment::r' from 'long long int' to 'int' [-Wnarrowing]
  424 |                 st.set({segm.l, segm.r, segm.l, segm.r}, qq);
      |                                 ~~~~~^
street_lamps.cpp:424:46: warning: narrowing conversion of 'segm.Containers::Segment::l' from 'long long int' to 'int' [-Wnarrowing]
  424 |                 st.set({segm.l, segm.r, segm.l, segm.r}, qq);
      |                                         ~~~~~^
street_lamps.cpp:424:54: warning: narrowing conversion of 'segm.Containers::Segment::r' from 'long long int' to 'int' [-Wnarrowing]
  424 |                 st.set({segm.l, segm.r, segm.l, segm.r}, qq);
      |                                                 ~~~~~^

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