Submission #937070

#	Time	Username	Problem	Language	Result	Execution time	Memory
937070		LOLOLO	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	1147 ms	59892 KiB

street_lamps

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

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 3e5 + 100;

struct fen{
    const int N = 1e6 + 10;
    vector <ll> f;

    fen() {
        f.assign(N, 0);
    }

    void upd(int i, ll x) {
        for (; i < N; i += i & (-i))
            f[i] += x;
    }

    ll get(int i) {
        ll s = 0;
        for (; i; i -= i & (-i))
            s += f[i];

        return s;
    }
};

fen fsum, fnum;
vector < vector <int>> all;
ll ans[N];

bool cmp(vector <int>&a, vector <int>&b) {
    if (a[0] == b[0]) {
        return a.back() > b.back();
    }

    return a[0] > b[0];
}

void dnc(int l, int r) {
    if (l == r)
        return;

    int m = (l + r) / 2;
    dnc(l, m);
    dnc(m + 1, r);

    vector < vector <int>> save;
    for (int i = l; i <= m; i++) {
        if (all[i].back() == 1) {
            save.pb({all[i][1], all[i][2], all[i][3]});
        }
    }

    for (int i = m + 1; i <= r; i++) {
        if (all[i].back() == 0) {
            save.pb({all[i][1], all[i][2], all[i][3]});
        }
    }

    sort(all(save), cmp);
    for (auto x : save) {
        if (x.back() == 1) {
            fsum.upd(abs(x[1]), x[1]);
            if (x[1] >= 0) {
                fnum.upd(abs(x[1]), 1);
            } else {
                fnum.upd(abs(x[1]), -1);
            }
        } else {
            ll cur = fsum.get(x[1]);
            if (fnum.get(x[1]) != 0) {
                cur += x[1] + 1;
            }

            ans[x[1]] += cur;
        }
    }

    for (auto x : save) {
        if (x.back() == 1) {
            fsum.upd(abs(x[1]), -x[1]);
            if (x[1] >= 0) {
                fnum.upd(abs(x[1]), -1);
            } else {
                fnum.upd(abs(x[1]), 1);
            }
        } 
    }
}

bool is[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;
    s = "0" + s + "0";

    set <int> st;
    
    for (int i = 0; i < len(s); i++) {
        if (s[i] == '0') {
            if (i) {
                int p = *(--st.end()) + 1;
                if (p <= i - 1) {
                    all.pb({p, i - 1, -2, 1});
                }
            }
            st.insert(i);
        }
    }

    for (int i = 2; i <= q + 1; i++) {
        string t;
        cin >> t;

        if (t[0] == 't') {
            int p;
            cin >> p;

            if (s[p] == '0') {
                st.erase(p);
                s[p] = '1';
                auto it = st.lower_bound(p);
                int r = (*it) - 1, l = (*prev(it)) + 1;
                all.pb({l, r, -i - 1, 1});

                if (p - 1 >= l) {
                    all.pb({l, p - 1, i + 1, 1});
                }

                if (p + 1 <= r) {
                    all.pb({p + 1, r, i + 1, 1});
                }
            } else {
                auto it = st.lower_bound(p);
                int r = (*it) - 1, l = (*prev(it)) + 1;
                all.pb({l, r, i + 1, 1});

                if (p - 1 >= l) {
                    all.pb({l, p - 1, -i - 1, 1});
                }

                if (p + 1 <= r) {
                    all.pb({p + 1, r, -i - 1, 1});
                }

                s[p] = '0';
                st.insert(p);
            }
        } else {
            is[i] = 1;
            int a, b;
            cin >> a >> b;
            all.pb({a, b - 1, i, 0});
        }
    }

    sort(all(all), [&](vector <int> &a, vector <int> &b) {return a[0] == b[0] ? a.back() > b.back() : a[0] < b[0];});
    dnc(0, sz(all) - 1);

    for (int i = 2; i <= q + 1; i++) {
        if (is[i] == 1) {
            cout << ans[i] << '\n';
        }
    }
}

/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

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