Submission #1234238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234238		t_holl	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	5092 ms	21580 KiB

street_lamps

#include <bits/stdc++.h>
#define int long long

#define MULTITEST false

using namespace std;

#define OPEN 0
#define CLOSE 1

struct SumSegTree {
    vector<int> tree;
    
    int size, start, height;

    SumSegTree (int _size) {
        size = _size;
        height = ceil(log2(size));
        start = 1 << height;

        tree.resize(start << 1);
    }

    void add (int node, int delta) {
        node += start;

        while (node != 0) {
            tree[node] += delta;
            node >>= 1;
        }
    }
    int sum (int l, int r) {
        l += start;
        r += start;

        int res = 0;

        while (l < r) {
            if ((l & 1) == 1) res += tree[l];
            if ((r & 1) == 0) res += tree[r];

            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) res += tree[l];
        return res;
    }
};

struct ItvEvent {
    int type;
    int l, r;
};
struct ItvManager {
    SumSegTree tree;

    vector<ItvEvent> operations;

    ItvManager (string buffer) : tree(buffer.size()) {
        for (int i = 0; i < buffer.size(); i ++) {
            if (buffer[i] == '0') continue ;

            tree.add(i, 1);
        }

        for (int i = 0; i < buffer.size(); i ++) {
            if (buffer[i] == '0') continue ;

            int right = find_right(i);
            operations.push_back({ OPEN, i, right });
            
            i = right;
        }
    }

    int find_right (int i) {
        int a = i;
        int b = tree.size;

        while (b - a > 1) {
            int m = (a + b) >> 1;

            if (tree.sum(a, m) != m - a + 1) b = m;
            else a = m;
        }

        return a;
    }
    int find_left (int i) {
        int a = -1;
        int b = i;

        while (b - a > 1) {
            int m = (a + b) >> 1;

            if (tree.sum(m, b) != b - m + 1) a = m;
            else b = m;
        }

        return b;
    }

    void enable (int node) {
        tree.add(node, 1);

        int left  = find_left(node);
        int right = find_right(node);
        
        if (left != node)
            operations.push_back({ CLOSE, left, node - 1 });
        if (right != node)
            operations.push_back({ CLOSE, node + 1, right });
            
        operations.push_back({ OPEN, left, right });
    }
    void disable (int node) {
        int left  = find_left(node);
        int right = find_right(node);
    
        operations.push_back({ CLOSE, left, right });

        tree.add(node, - 1);

        if (left != node)
            operations.push_back({ OPEN, left, node - 1 });
        if (right != node)
            operations.push_back({ OPEN, node + 1, right });
    }
    void toggle (int node) {
        if (tree.sum(node, node) == 0) {
            enable(node);
        } else {
            disable(node);
        }
    }
};

void display_time (int time) {
    cout << "=== TIME " << time << " ===\n";
}
void display_operation (ItvEvent &event) {
    cout << event.l << " " << event.r;

    if (event.type == OPEN) cout << ": OPEN\n";
    else cout << ": CLOSE\n";
}

struct QueryManager {
    int time;

    map<pair<int, int>, pair<int, bool>> payload;

    void set_time (int _time) {
        time = _time;
        //display_time(time);
    }
    void import (vector<ItvEvent> &events) {
        for (ItvEvent &event : events) {
            //display_operation(event);
            const pair<int, int> vpair = { event.l, event.r };

            pair<int, bool> data = payload[vpair];

            if (event.type == OPEN) {
                //cout << "NEW = " << data.first - time << " + time" << endl;
                payload[vpair] = { data.first - time, true };
            } else {
                //cout << "NEW = " << data.first + time << endl;;
                payload[vpair] = { data.first + time, false };
            }
        }

        events.clear();
    }
    int query (int left, int right) {
        //cout << "QUERY " << left << " " << right << endl;
        int res = 0;
        for (auto u : payload) {
            //cout << u.first.first << " " << u.first.second << ": " << u.second.first;
            //if (u.second.second) cout << " + time";
            //cout << endl;
            if (u.first.first <= left && right <= u.first.second) {

                //cout << " - USE\n";
                res += u.second.first;

                if (u.second.second)
                    res += time;
            }
        }

        return res;
    }
};

void solve () {
    int N, Q; cin >> N >> Q;

    string buffer;
    cin >> buffer;

    ItvManager itv_manager(buffer);
    QueryManager r_manager;

    r_manager.set_time(0);
    r_manager.import(itv_manager.operations);
    
    for (int t = 1; t <= Q; t ++) {
        r_manager.set_time(t);

        string type;
        cin >> type;
        
        if (type == "toggle") {
            int u;
            cin >> u;

            itv_manager.toggle(u - 1);
        } else {
            int l, r;
            cin >> l >> r;

            int res = r_manager.query(l - 1, r - 2);
            cout << res << "\n";
        }

        r_manager.import(itv_manager.operations);
    }
}

signed main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T = 1;
    if (MULTITEST) cin >> T;

    for (int t = 0; t < T; t ++) solve();
}

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