Submission #977828

#	Time	Username	Problem	Language	Result	Execution time	Memory
977828		ZHIRDILBILDIZ	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	719 ms	170936 KiB

street_lamps

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>

using namespace std;
const int N = 3e5 + 10;

int p[N];
int ans[N];
set<int> qr[N];
vector<int> gr[N];
void init(int _sz) {
    for (int i = 1; i <= _sz; ++i)
        p[i] = i,
            gr[i].push_back(i);
}
void join (int u, int v, int w) {
    u = p[u];
    v = p[v];
    if (u == v)
        return;
    if (gr[u].size() + qr[u].size() > gr[v].size() + qr[v].size())
        swap(u, v);
    for (int i : gr[u]) {
        p[i] = v;
        gr[v].push_back(i);
    }
    for (int i : qr[u])
        if (qr[v].find(i) != qr[v].end())
            ans[i] = max(ans[i], i - w);
        else
            qr[v].insert(i);
}
signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t = 1;
    while (t--) {
        int n, q;
        cin >> n >> q;
        char a[n + 1];
        char for_sub3[n + 1];
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            for_sub3[i] = a[i];
        }
        bool sub2 = 1;
        bool sub3 = 1;
        string type[q + 1];
        int c[q + 1], d[q + 1];
        bool abu[q + 1] = {};

        for (int i = 1; i <= q; ++i) {
            cin >> type[i] >> c[i];
            if (type[i] == "query") {
                cin >> d[i];
                abu[i] = 1;
                if (d[i] - c[i] != 1)
                    sub2 = 0;
            } else {
                if (for_sub3[c[i]] == '1')
                    sub3 = 0;
                else
                    for_sub3[c[i]] = '1';
            }
        }

        if (sub3) {
            init(n + 1);

            for (int i = 1; i <= q; ++i)
                if (type[i] == "query")
                    qr[c[i]].insert(i),
                        qr[d[i]].insert(i);

            for (int i = 1; i <= n; ++i)
                if (a[i] == '1')
                    join(i, i + 1, 0);

            for (int i = 1; i <= q; ++i)
                if (type[i] == "toggle")
                    join(c[i], c[i] + 1, i);

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

        if (sub2) {
            vector<pair<bool, int>> query[n + 1];

            for (int i = 1; i <= q; ++i)
                if (type[i] == "toggle")
                    query[c[i]].push_back({0, i});
                else
                    query[c[i]].push_back({1, i});

            for (int i = 1; i <= n; ++i) {
                pair<char, int> now = {a[i], 0};
                int cnt = 0;
                now = {a[i], 0};
                for (auto j : query[i]) {
                    if (j.fi) {
                        ans[j.se] = cnt + (now.fi == '1') * (j.se - now.se);
                    } else {
                        if (now.fi == '1') {
                            cnt += (j.se - now.se);
                            now.fi = '0';
                        } else {
                            now.fi = '1';
                        }
                        now.se = j.se;
                    }
                }
            }
            for (int i = 1; i <= q; ++i)
                if (abu[i])
                    cout << ans[i] << '\n';
            continue;
        }

        if (n <= 100 && q <= 100) {
            bool b[n + 1][q + 1] = {};
            for (int j = 1; j <= n; ++j)
                b[j][0] = a[j] - '0';
            for (int i = 1; i <= q; ++i) {
                if (type[i] == "toggle") {
                    if (a[c[i]] == '1')
                        a[c[i]] = '0';
                    else
                        a[c[i]] = '1';
                }
                for (int j = 1; j <= n; ++j)
                    b[j][i] = a[j] - '0';
                if (type[i] == "query") {
                    int ans = 0;
                    for (int j = 0; j < i; ++j) {
                        bool flag = 1;
                        for (int z = c[i]; z < d[i]; ++z)
                            flag &= (b[z][j]);
                        ans += flag;
                    }
                    cout << ans << '\n';
                }
            }
            continue;
        }

    }

    return 0;
}

// 10 9
// 1101110100
// query 1 2
// toggle 3 
// query 1 6
// query 1 6
// toggle 10
// query 10 11
// query 9 10
// toggle 9
// query 9 10

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