Submission #1143905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143905		Nelt	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	1718 ms	397060 KiB

street_lamps

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
struct FenwickTree
{
    ll n, tot;
    vector<ll> t;
    FenwickTree(ll x = 0)
    {
        n = x;
        tot = 0;
        t.resize(n + 1, 0);
    }
    ll sum(ll i)
    {
        ll res = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1)
            res += t[i];
        return res;
    }
    void upd(ll i, ll d)
    {
        tot += d;
        for (; i <= n; i = (i | (i + 1)))
            t[i] += d;
    }
    ll suf(ll i)
    {
        return tot - sum(i - 1);
    }
};
struct SegTree
{
    ll n;
    vector<FenwickTree> st;
    vector<vector<ll>> comp;
    SegTree(ll x = 0)
    {
        n = x;
        comp.resize(n << 2);
        st.resize(n << 2);
    }
    void set(ll i, ll j, ll l, ll r, ll v)
    {
        if (max(i, l) > min(j, r))
            return;
        if (i <= l and r <= j)
        {
            comp[v].push_back(j + 1);
            return;
        }
        ll mid = (l + r) >> 1;
        set(i, j, l, mid, v << 1);
        set(i, j, mid + 1, r, v << 1 | 1);
    }
    void build()
    {
        for (ll i = 1; i < (n << 2); i++)
        {
            sort(comp[i].begin(), comp[i].end());
            comp[i].resize(unique(comp[i].begin(), comp[i].end()) - comp[i].begin());
            st[i] = FenwickTree(comp[i].size());
        }
    }
    void modify(ll i, ll j, ll d, ll l, ll r, ll v)
    {
        if (max(i, l) > min(j, r))
            return;
        if (i <= l and r <= j)
        {
            st[v].upd(lower_bound(comp[v].begin(), comp[v].end(), j + 1) - comp[v].begin(), d);
            return;
        }
        ll mid = (l + r) >> 1;
        modify(i, j, d, l, mid, v << 1);
        modify(i, j, d, mid + 1, r, v << 1 | 1);
    }
    ll query(ll i, ll j, ll l, ll r, ll v)
    {
        if (l == r)
            return st[v].suf(lower_bound(comp[v].begin(), comp[v].end(), j) - comp[v].begin());
        ll mid = (l + r) >> 1;
        if (i <= mid)
            return query(i, j, l, mid, v << 1) + st[v].suf(lower_bound(comp[v].begin(), comp[v].end(), j) - comp[v].begin());
        else
            return query(i, j, mid + 1, r, v << 1 | 1) + st[v].suf(lower_bound(comp[v].begin(), comp[v].end(), j) - comp[v].begin());
    }
} st[2];
const ll N = 3e5 + 5;
string s;
set<pair<ll, ll>> seg;
ll n, q;
void addseg(ll l, ll r, ll d, ll t)
{
    if (!t)
    {
        st[0].modify(l, r, d, 1, n + 1, 1);
        st[1].modify(l, r, 1, 1, n + 1, 1);
    }
    else
    {
        st[0].set(l, r, 1, n + 1, 1);
        st[1].set(l, r, 1, n + 1, 1);
    }
}
void removeseg(ll l, ll r, ll d, ll t)
{
    if (!t)
    {
        st[0].modify(l, r, -d, 1, n + 1, 1);
        st[1].modify(l, r, -1, 1, n + 1, 1);
    }
    else
    {
        st[0].set(l, r, 1, n + 1, 1);
        st[1].set(l, r, 1, n + 1, 1);
    }
}
void add(ll x, ll t, ll d)
{
    auto it = seg.upper_bound(make_pair(x, 1e9));
    ll l = x, r = x;
    if (it != seg.begin())
    {
        --it;
        if (it->second == x - 1)
        {
            l = it->first;
            removeseg(l, x - 1, d, t);
            seg.erase(it);
        }
    }
    it = seg.upper_bound(make_pair(x, 1e9));
    if (it != seg.end())
    {
        if (it->first == x + 1)
        {
            r = it->second;
            removeseg(x + 1, r, d, t);
            seg.erase(it);
        }
    }
    addseg(l, r, d, t);
    // cout << l << " " << r << " " << x << endl;
    seg.insert(make_pair(l, r));
}
void remove(ll x, ll t, ll d)
{
    auto it = --seg.upper_bound(make_pair(x, 1e9));
    ll l = it->first, r = it->second;
    seg.erase(it);
    removeseg(l, r, d, t);
    if (l <= x - 1)
    {
        seg.insert(make_pair(l, x - 1));
        addseg(l, x - 1, d, t);
    }
    if (x + 1 <= r)
    {
        seg.insert(make_pair(x + 1, r));
        addseg(x + 1, r, d, t);
    }
}
void solve()
{
    cin >> n >> q;
    cin >> s;
    s = ' ' + s;
    array<ll, 2> qs[q + 1];
    for (ll i = 1; i <= q; i++)
    {
        string s;
        cin >> s;
        if (s == "toggle")
            cin >> qs[i][0], qs[i][1] = -1;
        else
            cin >> qs[i][0] >> qs[i][1];
    }
    st[0] = st[1] = SegTree(n + 1);
    {
        string b = s;
        // for (ll i = 1; i <= n; i++) 
        for (ll i = 1; i <= n; i++)
            if (b[i] == '1')
                add(i, 1, 0);
        for (ll i = 1; i <= q; i++)
            if (qs[i][1] == -1)
            {
                ll ind = qs[i][0];
                if (b[ind] == '1')
                    remove(ind, 1, i), b[ind] = '0';
                else add(ind, 1, i), b[ind] = '1';
            }
        st[0].build();
        st[1].build();
    }
    seg.clear();
    for (ll i = 1; i <= n; i++) if (s[i] == '1') add(i, 0, 0);
    for (ll i = 1; i <= q; i++) if (qs[i][1] == -1)
    {
        ll ind = qs[i][0];
                if (s[ind] == '1')
                    remove(ind, 0, i), s[ind] = '0';
                else add(ind, 0, i), s[ind] = '1';
    }
    else
        cout << st[1].query(qs[i][0], qs[i][1], 1, n + 1, 1) * i - st[0].query(qs[i][0], qs[i][1], 1, n + 1, 1) << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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