Submission #545528

#	Time	Username	Problem	Language	Result	Execution time	Memory
545528		Ooops_sorry	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	5033 ms	42132 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define ld double
#define ll __int128

mt19937 rnd(51);

const int INF = 1e18;

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> s(n);
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        s[i] = c - '0';
    }
    vector<int> time(n);
    vector<vector<pair<int,int>>> seg(n), need(n);
    vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        string t;
        cin >> t;
        if (t == "toggle") {
            int j;
            cin >> j;
            j--;
            if (s[j] == 0) {
                seg[j].pb({time[j], i});
            }
            time[j] = i + 1;
            s[j] ^= 1;
            ans[i] = -1;
        } else {
            int l, r;
            cin >> l >> r;
            l--, r -= 2;
            need[l].pb({r, i});
            ans[i] = i + 1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (s[i] == 0) {
            seg[i].pb({time[i], q - 1});
        }
    }
    vector<int> val(q, INF);
    for (int i = n - 1; i >= 0; i--) {
        for (auto to : seg[i]) {
            for (int j = to.first; j <= to.second; j++) {
                val[j] = i;
            }
        }
        for (auto to : need[i]) {
            for (int j = 0; j <= to.second; j++) {
                if (val[j] <= to.first) {
                    ans[to.second]--;
                }
            }
        }
    }
    for (int i = 0; i < q; i++) {
        if (ans[i] != -1) {
            cout << ans[i] << endl;
        }
    }
    return 0;
}

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