Submission #391310

#	Time	Username	Problem	Language	Result	Execution time	Memory
391310		phathnv	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	2790 ms	100168 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 7;

struct Query{
    int type, a, b;
};

struct Bit2D{
    vector<int> nodes[N], d[N];
    void fakeUpdate(int x, int y){
        for(; x < N; x += x & -x)
            nodes[x].push_back(y);
    }
    void fakeQuery(int x, int y){
        for(; x > 0; x -= x & -x)
            nodes[x].push_back(y);
    }
    void normalize(){
        for(int i = 1; i < N; i++){
            sort(nodes[i].begin(), nodes[i].end());
            nodes[i].resize(unique(nodes[i].begin(), nodes[i].end()) - nodes[i].begin());
            d[i].assign(nodes[i].size() + 1, 0);
        }
    }
    void update(int x, int y, int val){
        for(; x < N; x += x & -x){
            int p = lower_bound(nodes[x].begin(), nodes[x].end(), y) - nodes[x].begin() + 1;
            for(; p <= (int) nodes[x].size(); p += p & -p)
                d[x][p] += val;
        }
    }
    int query(int x, int y){
        int res = 0;
        for(; x > 0; x -= x & -x){
            int p = lower_bound(nodes[x].begin(), nodes[x].end(), y) - nodes[x].begin() + 1;
            for(; p > 0; p -= p & -p)
                res += d[x][p];
        }
        return res;
    }
} bit;

int n, q, last[N];
Query queries[N];
string s, cur;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q >> s;
    s = '*' + s;
    for(int i = 1; i <= q; i++){
        string p;
        cin >> p;
        if (p == "query"){
            queries[i].type = 0;
            cin >> queries[i].a >> queries[i].b;
            queries[i].b--;
        } else {
            queries[i].type = 1;
            cin >> queries[i].a;
        }
    }

    cur = s;
    set<int> empPos;
    for(int i = 1; i <= n; i++){
        last[i] = 0;
        if (cur[i] == '0')
            empPos.insert(i);
    }
    empPos.insert(0);
    empPos.insert(n + 1);
    for(int i = 1; i <= q; i++){
        if (queries[i].type == 0){
            bit.fakeQuery(queries[i].a, queries[i].b);
        } else {
            int pos = queries[i].a;
            if (cur[pos] == '0'){
                empPos.erase(pos);
                auto it = empPos.lower_bound(pos);
                int r = *it;
                int l = *(--it);
                if (l + 1 <= pos - 1){
                    bit.fakeUpdate(l + 1, l + 1);
                    bit.fakeUpdate(l + 1, pos);
                }
                if (pos + 1 <= r - 1)
                    bit.fakeUpdate(pos + 1, pos + 1);
                    bit.fakeUpdate(pos + 1, r);
                cur[pos] = '1';
            } else {
                auto it = empPos.lower_bound(pos);
                int r = *it;
                int l = *(--it);
                if (l + 1 <= r - 1)
                    bit.fakeUpdate(l + 1, r - 1);
                empPos.insert(pos);
                cur[pos] = '0';
            }
        }
    }

    bit.normalize();
    cur = s;
    empPos.clear();
    for(int i = 1; i <= n; i++){
        last[i] = 0;
        if (cur[i] == '0')
            empPos.insert(i);
    }
    empPos.insert(0);
    empPos.insert(n + 1);
    for(int i = 1; i <= q; i++){
        if (queries[i].type == 0){
            int res = bit.query(queries[i].a, queries[i].b);
            auto it = empPos.lower_bound(queries[i].a);
            if (*it > queries[i].b)
                res += (i - last[*(--it) + 1]);
            cout << res << '\n';
        } else {
            int pos = queries[i].a;
            if (cur[pos] == '0'){
                empPos.erase(pos);
                auto it = empPos.lower_bound(pos);
                int r = *it;
                int l = *(--it);
                if (l + 1 <= pos - 1){
                    int num = i - last[l + 1];
                    bit.update(l + 1, l + 1, num);
                    bit.update(l + 1, pos, -num);
                    last[l + 1] = i;
                }
                if (pos + 1 <= r - 1){
                    int num = i - last[pos + 1];
                    bit.update(pos + 1, pos + 1, num);
                    bit.update(pos + 1, r, -num);
                    last[pos + 1] = i;
                }
                cur[pos] = '1';
                last[pos] = i;
            } else {
                auto it = empPos.lower_bound(pos);
                int r = *it;
                int l = *(--it);
                if (l + 1 <= r - 1){
                    int num = i - last[l + 1];
                    bit.update(l + 1, l + 1, num);
                    bit.update(l + 1, r, -num);
                    last[l + 1] = i;
                }
                last[pos + 1] = i;
                empPos.insert(pos);
                cur[pos] = '0';
            }
        }
    }

    return 0;
}

/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:93:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   93 |                 if (pos + 1 <= r - 1)
      |                 ^~
street_lamps.cpp:95:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   95 |                     bit.fakeUpdate(pos + 1, r);
      |                     ^~~

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