Submission #583660

#	Time	Username	Problem	Language	Result	Execution time	Memory
583660		training4usaco	Street Lamps (APIO19_street_lamps)	C++11	0 / 100	576 ms	4964 KiB

street_lamps

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

struct Segtree {
    struct Node {
        int sum = 0, lc = 0, rc = 0;
        Node() {}
        Node(int num) : sum(num) {}

        void addsum(const Node &l, const Node &r) {
            sum = l.sum + r.sum;
        }

    };

    vector<Node> nodes;
    int n;

    int new_node() {
        nodes.emplace_back();
        return nodes.size() - 1;
    }

    void update(int node, int left, int right, int idx, int val) {
        if(left == idx && idx == right) {
            nodes[node].sum += val;
            return;
        }

        int mid = (left + right) / 2;

        if(idx <= mid) {
            if (!nodes[node].lc) {
                nodes[node].lc = new_node();
            }

            update(nodes[node].lc, left, mid, idx, val);
        }
        if(idx > mid) {
            if (!nodes[node].rc) {
                nodes[node].rc = new_node();
            }

            update(nodes[node].rc, mid + 1, right, idx, val);
        }

        nodes[node].addsum(nodes[nodes[node].lc], nodes[nodes[node].rc]);
    }

    void add(int index, int val) {
        update(1, 0, n - 1, index, val);
    }

    Node query(int node, int left, int right, int x, int y) {
        if(node == 0) {
            return {};
        }

        if(x <= left && right <= y) {
            return nodes[node];
        }

        int mid = (left + right) / 2;

        if(y <= mid) {
            return query(nodes[node].lc, left, mid, x, y);
        }
        else if(x > mid) {
            return query(nodes[node].rc, mid + 1, right, x, y);
        }

        return Node(query(nodes[node].lc, left, mid, x, y).sum + query(nodes[node].rc, mid + 1, right, x, y).sum);
    }

    int query_sum(int l, int r) {
        return query(1, 0, n - 1, l, r).sum;
    }

    Segtree(int _n) : n(_n) {
        nodes.emplace_back();
        nodes.emplace_back();
    }
    Segtree() {}
};


struct BIT {
    int maxsz;
    vector<Segtree> bit;

    void add(int r, int c, int v) {
        if (r == maxsz || c == maxsz) {
            return;
        }

        for (++r; r <= maxsz; r += (r & -r)) {
            bit[r].add(c, v);
        }
    }

    void submatrixadd(int r1, int c1, int r2, int c2, int to_add) {
        add(r2 + 1, c2 + 1, to_add);
        add(r2 + 1, c1, -to_add);
        add(r1, c2 + 1, -to_add);
        add(r1, c1, to_add);
    }

    int psum(int r, int c) {
        int ret = 0;

        for (++r; r; r -= (r & -r)) {
            ret += bit[r].query_sum(0, c);
        }

        return ret;
    }

    BIT(int rows, int cols) : maxsz(rows) {
        bit.resize(maxsz + 1);
        for (int i = 1; i <= maxsz; ++i) {
            bit[i] = Segtree(cols);
        }
    }
};

int main() {
    int n, q;
    string lightstatus;
    set<int> off;

    cin >> n >> q;
    cin >> lightstatus;

    BIT bit(n + 1, n + 1);

    int start = -1;

    for (int i = 0; i < n; ++i) {
        if (lightstatus[i] == '1') {
            if (start == -1) {
                start = i;
            }

            if (i == n - 1) {
                bit.submatrixadd(start, start, i + 1, i + 1, q);
            }
        }
        else {
            off.insert(i);

            if (start != -1) {
                bit.submatrixadd(start, start, i, i, q);
            }

            start = -1;
        }
    }

    off.insert(-1);
    off.insert(n);

    for (int i = 0, a, b; i < q; ++i) {
        string type;
        cin >> type;

        int remaintime = q - (i + 1);

        if (type == "toggle") {
            cin >> a;
            --a;

            int l = *prev(off.lower_bound(a)) + 1;
            int r = *off.upper_bound(a);

            if(lightstatus[a] == '0') {
                bit.submatrixadd(a + 1, l, r, a, remaintime);
            }
            else {
                bit.submatrixadd(a + 1, l, r, a, -1 * remaintime);
            }

            if (lightstatus[a] == '1') {
                off.insert(a);
                lightstatus[a] = '0';
            } 
            else {
                off.erase(a);
                lightstatus[a] = '1';
            }
        } 
        else {
            cin >> a >> b;
            --a;
            --b;

            if (a < b) {
                swap(a, b);
            }

            if (off.lower_bound(a) == off.lower_bound(b)) {
                cout << bit.psum(a, b) - remaintime << '\n';    // overcount
            } 
            else {
                cout << bit.psum(a, b) << endl;
            }
        }
    }

    return 0;
}

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