Submission #1281106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281106		windowwife	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	2734 ms	171848 KiB

street_lamps

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 3e5 + 2;
int n, q, a[maxn], b[maxn], x[maxn];
char c[maxn], c2[maxn];
string tp[maxn];
struct SegmentTree
{
    int st[2*maxn];
    void build (int node, int l, int r)
    {
        if (l == r)
        {
            st[node] = l;
            return;
        }
        int m = (l + r)/2;
        build(node + 1, l, m);
        build(node + 2 * (m - l + 1), m + 1, r);
        st[node] = 0;
    }
    void down (int node, int l, int m)
    {
        if (st[node] == 0) return;
        st[node + 1] = st[node];
        st[node + 2 * (m - l + 1)] = st[node];
        st[node] = 0;
    }
    void upd (int node, int l, int r, int cl, int cr, int val)
    {
        if (cr < l || r < cl) return;
        if (cl <= l && r <= cr)
        {
            st[node] = val;
            return;
        }
        int m = (l + r)/2;
        down(node, l, m);
        upd(node + 1, l, m, cl, cr, val);
        upd(node + 2 * (m - l + 1), m + 1, r, cl, cr, val);
    }
    int get (int node, int l, int r, int idx)
    {
        if (l == r) return st[node];
        int m = (l + r)/2;
        down(node, l, m);
        if (idx <= m) return get(node + 1, l, m, idx);
        return get(node + 2 * (m - l + 1), m + 1, r, idx);
    }
}st[2];
struct BIT2D
{
    vector<int> pos[maxn], fw[maxn];
    BIT2D()
    {
        for (int i = 0; i < maxn; i++)
        {
            pos[i].clear();
            fw[i].clear();
        }
    }
    void fakeupd (int i, int j)
    {
        for (; i < maxn; i += (i & (-i)))
            pos[i].push_back(j);
    }
    void fakeget (int i, int j)
    {
        for (; i > 0; i -= (i & (-i)))
            pos[i].push_back(j);
    }
    void compress ()
    {
        for (int i = 0; i < maxn; i++)
        {
            sort(pos[i].begin(), pos[i].end());
            pos[i].resize(unique(pos[i].begin(), pos[i].end()) - pos[i].begin());
            fw[i].resize(pos[i].size() + 1, 0);
        }
    }
    void upd (int i, int j, int val)
    {
        for (; i < maxn; i += (i & (-i)))
            for (int k = lower_bound(pos[i].begin(), pos[i].end(), j) - pos[i].begin() + 1; k <= (int)pos[i].size(); k += (k & (-k)))
                fw[i][k] += val;
    }
    int get (int i, int j)
    {
        int res = 0;
        for (; i > 0; i -= (i & (-i)))
            for (int k = lower_bound(pos[i].begin(), pos[i].end(), j) - pos[i].begin() + 1; k > 0; k -= (k & (-k)))
                res += fw[i][k];
        return res;
    }
}bit2d;
void fakeconnect (int x)
{
    int l = st[0].get(1, 1, n + 1, x), r = st[1].get(1, 1, n + 1, x + 1);
    st[1].upd(1, 1, n + 1, l, x, r);
    st[0].upd(1, 1, n + 1, x + 1, r, l);
    bit2d.fakeupd(l, x + 1);
    bit2d.fakeupd(l, r + 1);
    bit2d.fakeupd(x + 1, x + 1);
    bit2d.fakeupd(x + 1, r + 1);
}
void fakedisconnect (int x)
{
    int l = st[0].get(1, 1, n + 1, x), r = st[1].get(1, 1, n + 1, x + 1);
    st[1].upd(1, 1, n + 1, l, x, x);
    st[0].upd(1, 1, n + 1, x + 1, r, x + 1);
    bit2d.fakeupd(l, x + 1);
    bit2d.fakeupd(l, r + 1);
    bit2d.fakeupd(x + 1, x + 1);
    bit2d.fakeupd(x + 1, r + 1);
}
void connect (int x, int t)
{
    int l = st[0].get(1, 1, n + 1, x), r = st[1].get(1, 1, n + 1, x + 1);
    st[1].upd(1, 1, n + 1, l, x, r);
    st[0].upd(1, 1, n + 1, x + 1, r, l);
    bit2d.upd(l, x + 1, q - t);
    bit2d.upd(l, r + 1, t - q);
    bit2d.upd(x + 1, x + 1, t - q);
    bit2d.upd(x + 1, r + 1, q - t);
}
void disconnect (int x, int t)
{
    int l = st[0].get(1, 1, n + 1, x), r = st[1].get(1, 1, n + 1, x + 1);
    st[1].upd(1, 1, n + 1, l, x, x);
    st[0].upd(1, 1, n + 1, x + 1, r, x + 1);
    bit2d.upd(l, x + 1, t - q);
    bit2d.upd(l, r + 1, q - t);
    bit2d.upd(x + 1, x + 1, q - t);
    bit2d.upd(x + 1, r + 1, t - q);
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    st[0].build(1, 1, n + 1);
    st[1].build(1, 1, n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> c[i];
        c[i] -= '0';
        if (c[i] == 1) fakeconnect(i);
        c2[i] = c[i];
    }
    for (int i = 1; i <= q; i++)
    {
        cin >> tp[i];
        if (tp[i] == "toggle")
        {
            cin >> x[i];
            if (c[x[i]] == 0) fakeconnect(x[i]);
            else fakedisconnect(x[i]);
            c[x[i]] ^= 1;
        }
        else
        {
            cin >> a[i] >> b[i];
            bit2d.fakeget(a[i], b[i]);
        }
    }
    bit2d.compress();
    st[0].build(1, 1, n + 1);
    st[1].build(1, 1, n + 1);
    for (int i = 1; i <= n; i++)
    {
        if (c2[i] == 1) connect(i, 0);
    }
    for (int i = 1; i <= q; i++)
    {
        if (tp[i] == "toggle")
        {
            if (c2[x[i]] == 0) connect(x[i], i);
            else disconnect(x[i], i);
            c2[x[i]] ^= 1;
        }
        else
        {
            int l1 = st[0].get(1, 1, n + 1, a[i]), l2 = st[0].get(1, 1, n + 1, b[i]), ans = bit2d.get(a[i], b[i]);
            if (l1 != l2) cout << ans << '\n';
            else cout << ans - (q - i) << '\n';
        }
    }
}

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