Submission #1035194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035194		stdfloat	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	432 ms	36292 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define ff  first
#define ss  second
#define pii pair<int, int>

vector<int> st, lz;

void LZ(int nd, int l, int r) {
    st[nd] += lz[nd];

    if (l != r) {
        int ch = (nd << 1) + 1;
        lz[ch] += lz[nd];
        lz[ch + 1] += lz[nd];
    }

    lz[nd] = 0;
}

int upd(int nd, int l, int r, int x, int y, int vl) {
    LZ(nd, l, r);
    
    if (y < l || r < x) return st[nd];

    if (x <= l && r <= y) {
        lz[nd] = vl; LZ(nd, l, r);
        return st[nd];
    }

    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    return st[nd] = upd(ch, l, md, x, y, vl) + upd(ch + 1, md + 1, r, x, y, vl);
}

int fnd(int nd, int l, int r, int x) {
    LZ(nd, l, r);

    if (r < x || x < l) return 0;

    if (l == r) return st[nd];

    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    return fnd(ch, l, md, x) + fnd(ch + 1, md + 1, r, x);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, q;
    string s;
    cin >> n >> q >> s;

    set<int> zr = {-1, n};
    vector<pair<pii, pii>> v;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') zr.insert(i);
        else {
            int r = i;
            while (r + 1 < n && s[r + 1] == '1') r++;

            v.push_back({{i, -1}, {i, r}});
            v.push_back({{r + 1, 1}, {i, r}});

            i = r;
        }
    }

    bool tr = false;
    for (int z = 2; z <= q + 1; z++) {
        string t;
        cin >> t;

        if (t == "toggle") {
            int i;
            cin >> i; i--;

            int l = *--zr.lower_bound(i), r = *zr.upper_bound(i);
            if (s[i] == '0') {
                zr.erase(i);
                s[i] = '1';
                v.push_back({{l + 1, -z}, {i, r - 1}});
                v.push_back({{i + 1, z}, {i, r - 1}});
            }
            else {
                s[i] = '0';
                zr.insert(i);
                v.push_back({{l + 1, z}, {i, r - 1}});
                v.push_back({{i + 1, -z}, {i, r - 1}});
            }
        }
        else {
            int a, b;
            cin >> a >> b; a--; b--;

            v.push_back({{a, (int)1e8 + z}, {b, z}});
        }
    }

    sort(v.begin(), v.end());
    
    st.assign(n << 2, 0);
    lz.assign(n << 2, 0);
    vector<int> ans(q + 2, -1);
    for (auto i : v) {
        if (i.ff.ss <= (int)1e8) upd(0, 0, n - 1, i.ss.ff, i.ss.ss, i.ff.ss);
        else ans[i.ff.ss - (int)1e8] = fnd(0, 0, n - 1, i.ss.ff - 1) + (i.ss.ff <= *zr.lower_bound(i.ff.ff) ? i.ss.ss : 0);
    }

    for (auto i : ans) if (i != -1) cout << i << '\n';
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:71:10: warning: unused variable 'tr' [-Wunused-variable]
   71 |     bool tr = false;
      |          ^~

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