Submission #1044635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044635		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	102 ms	3156 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 3e5 + 100;

ll fen[MAXN], t = 0;
set<pair<int,pair<int,int>>> st;
set<int> zeros;
vector<int> A;
void add(int k, int val) {
    while (k < MAXN) {
        fen[k] += val;
        k += k & -k;
    }
}

int get(int k) {
    ll res = 0;
    while (k > 0) {
        res += fen[k];
        k -= k & -k;
    }
    return res;
}

void close_int(int l, int r, int open_time, int close_time) {
    st.erase({l, {0, open_time}});
    st.erase({r, {1, open_time}});
    add(l, close_time - open_time);
    add(r, - close_time + open_time);
}

void open_int(int l, int r, int t) {
    st.insert({l, {0, t}});
    st.insert({r, {1, t}});
}

int main() {
    fast
    int n, q;
    cin >> n >> q;

    A = vector<int>(n+2, 0);
    string s;
    cin >> s;
    for (int i = 1; i <= n; i++) {
        A[i] = s[i-1] - '0';
        if (A[i] == 0)
            zeros.insert(i);
    }

    for (int i = 1; i <= n; i++) {
        if (A[i-1] == 0 && A[i])
            st.insert({i, {0, 0}});
        if (A[i] && (i == n || A[i+1] == 0))
            st.insert({i, {1, 0}});
    }

    while (q--) {
        t++;
        string type;
        cin >> type;
        if (type == "toggle") {
            int x;
            cin >> x;

            if (A[x]) {
                auto u = st.lower_bound({x, {1, 0}});
                auto v = prev(u);
                int l = (*v).f, r = (*u).f, last_time = (*v).s.s;
                close_int(l, r, last_time, t-1);
                if (l <= x - 1)
                    open_int(l, x-1, t);
                if (x + 1 <= r)
                    open_int(x+1, r, t);
            } else {

                if (A[x-1] && A[x+1]) {
                    auto u_left = st.lower_bound({x-1, {1, 0}});
                    auto v_left = prev(u_left);
                    
                    auto u_right = st.lower_bound({x+1, {1, 0}});
                    auto v_right = prev(u_right);

                    close_int((*v_left).f, (*u_left).f, (*u_left).s.s, t-1);
                    close_int((*v_right).f, (*u_right).f, (*u_right).s.s, t-1);
                    open_int((*v_left).f, (*u_right).f, t);
                } else if (A[x-1]) {
                    auto u_left = st.lower_bound({x-1, {1, 0}});
                    auto v_left = prev(u_left);
                    
                    close_int((*v_left).f, (*u_left).f, (*u_left).s.s, t-1);
                    open_int((*v_left).f, x, t);
                } else if (A[x+1]) {
                    auto u_right = st.lower_bound({x+1, {1, 0}});
                    auto v_right = prev(u_right);

                    close_int((*v_right).f, (*u_right).f, (*u_right).s.s, t-1);
                    open_int(x, (*u_right).f, t);
                } else
                    open_int(x, x, t);

            }

            if (A[x] == 0)
                zeros.erase(x);
            else
                zeros.insert(x);

            A[x] ^= 1; 
            
        } else {
            int l, r;
            cin >> l >> r;
            r--;

            ll ans = get(r);

            if (zeros.lower_bound(l) == zeros.end() || *zeros.lower_bound(l) > r) {
                auto u = st.lower_bound({l, {1, 0}});
                auto v = prev(u);
                ans += t - (*u).s.s;
            }

            cout << ans << "\n";
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:127:22: warning: variable 'v' set but not used [-Wunused-but-set-variable]
  127 |                 auto v = prev(u);
      |                      ^

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