Submission #384185

#	Time	Username	Problem	Language	Result	Execution time	Memory
384185		valerikk	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	89 ms	4332 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;

int n, q;
string s;
int f[N][N], cnt[N][N];

void on(int a, int b, int t) {
    f[a][b] -= t;
    cnt[a][b]++;
}

void off(int a, int b, int t) {
    f[a][b] += t;
    cnt[a][b]--;
}

void toggle(int i, int t) {
    if (s[i] == '0') {
        int p = i, q = i + 1;
        while (p > 0 && s[p - 1] == '1') p--;
        while (q < n && s[q] == '1') q++;
        for (int a = p; a <= i; a++) {
            for (int b = i + 1; b <= q; b++) {
                on(a, b, t);
            }
        }

        s[i] = '1';
    } else {
        int p = i, q = i + 1;
        while (p > 0 && s[p - 1] == '1') p--;
        while (q < n && s[q] == '1') q++;
        for (int a = p; a <= i; a++) {
            for (int b = i + 1; b <= q; b++) {
                off(a, b, t);
            }
        }

        s[i] = '0';
    }
}

int query(int a, int b, int t) {
    return f[a][b] + t * cnt[a][b];
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q >> s;
    
    for (int i = 0; i < n; i++) {
        bool ok = 1;
        for (int j = i + 1; j <= n; j++) {
            if (s[j - 1] == '0') break;
            on(i, j, 0);
        }
    }

    for (int t = 1; t <= q; t++) {
        string type;
        cin >> type;
        if (type == "toggle") {
            int i;
            cin >> i;
            i--;
            toggle(i, t);
        } else {
            int a, b;
            cin >> a >> b;
            a--;
            b--;

            cout << query(a, b, t) << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:59:14: warning: unused variable 'ok' [-Wunused-variable]
   59 |         bool ok = 1;
      |              ^~

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