Submission #1234228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234228		t_holl	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	5095 ms	28332 KiB

street_lamps

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

#define MULTITEST false

using namespace std;

#define OPEN 0
#define CLOSE 1

struct ItvEvent {
    int type;
    int l, r;
};
struct ItvManager {
    vector<int> tree, segsize;

    int size, start, height;

    vector<ItvEvent> operations;

    ItvManager (string buffer) {
        size = buffer.size();
        height = ceil(log2(size));
        start = 1 << height;

        tree.resize(start << 1);
        segsize.resize(start << 1);

        for (int i = 0; i < size; i ++) {
            tree[i + start] = buffer[i] - '0';
            segsize[i + start] = 1;
        }
        
        for (int i = start - 1; i > 0; i --) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
            segsize[i] = segsize[2 * i] + segsize[2 * i + 1];
        }

        for (int i = 0; i < size; i ++) {
            if (tree[i + start] == 0) continue ;

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

    int find_right (int i) {
        // TODO speed up to O(log N)
        i += start;
        while (i < start + size && tree[i] == 1) {
            i ++;
        }

        return i - 1 - start;
    }
    int find_left (int i) {
        // TODO speed up to O(log N)
        i += start;
        while (i >= start && tree[i] == 1) {
            i --;
        }

        return i + 1 - start;
    }

    void update (int node, int del) {
        node += start;
        while (node != 0) {
            tree[node] += del;
            node >>= 1;
        }
    }

    void enable (int node) {
        update(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 });

        update(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[node + start] == 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