Submission #354154

#	Time	Username	Problem	Language	Result	Execution time	Memory
354154		parsabahrami	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3798 ms	134012 KiB

street_lamps

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 3e5 + 10, MOD = 1e9 + 7;
vector<int> F[N], vec[N]; set<pair<pii, int>> st, tmp;
int n, q, A[N], T[N], type[N], ql[N], qr[N]; char C[N];

void __init(int r, int c) {
    for (; r < N; r += r & -r) vec[r].push_back(c);
}

void init(int r, int c) {
    __init(r, r), __init(c + 1, c + 1), __init(r, c + 1), __init(c + 1, r);
}

void __upd(int r, int c, int x) {
    for (; r < N; r += r & -r) {
        int _c = lower_bound(vec[r].begin(), vec[r].end(), c) - vec[r].begin(); 
        for (; _c < SZ(F[r]); _c += _c & -_c) F[r][_c] += x;
    }
}

void upd(int r, int c, int x) {
    __upd(r, r, x), __upd(c + 1, c + 1, x), __upd(r, c + 1, -x), __upd(c + 1, r, -x);
}

int get(int r, int c) {
    int ret = 0;
    for (; r; r -= r & -r) {
        int _c = upper_bound(vec[r].begin(), vec[r].end(), c) - vec[r].begin() - 1;
        for (; _c; _c -= _c & -_c) ret += F[r][_c];
    }
    return ret;
}

void __erase(int x) {
    auto it = st.upper_bound({{x, MOD}, 0});
    if (it == st.begin()) return;
    it--;
    int l = it->F.F, r = it->F.S;
    init(l, r); st.erase(it);
    if (x > l) st.insert({{l, x - 1}, 0});
    if (x < r) st.insert({{x + 1, r}, 0});
}

void __add(int x) {
    int l = x, r = x;
    auto it = st.upper_bound({{x, MOD}, 0});
    if (it != st.end()) {
        if (it->F.F == x + 1) {
            init(x + 1, it->F.S); r = it->F.S, st.erase(it);
        }
    }
    it = st.upper_bound({{x, MOD}, 0}); 
    if (it != st.begin()) {
        it--;
        if (it->F.S == x - 1) {
            init(it->F.F, x - 1); l = it->F.F, st.erase(it);
        }
    }
    st.insert({{l, r}, 0});
}

void add(int x, int id) {
    int l = x, r = x;
    auto it = st.upper_bound({{x, MOD}, 0});
    if (it != st.end()) {
        if (it->F.F == x + 1) {
            upd(x + 1, it->F.S, id - it->S), r = it->F.S, st.erase(it);
        }
    }
    it = st.upper_bound({{x, MOD}, 0}); 
    if (it != st.begin()) {
        it--;
        if (it->F.S == x - 1) {
            upd(it->F.F, x - 1, id - it->S), l = it->F.F, st.erase(it);
        }
    }
    st.insert({{l, r}, id});
}

void erase(int x, int id) {
    auto it = st.upper_bound({{x, MOD}, 0});
    if (it == st.begin()) return;
    it--;
    int l =it->F.F, r = it->F.S;
    upd(l, r, id - it->S); st.erase(it);
    if (x > l) st.insert({{l, x - 1}, id});
    if (x < r) st.insert({{x + 1, r}, id});
}

int main() {
    scanf("%d%d\n%s", &n, &q, C + 1);
    for (int i = 1; i <= n; i++) A[i] = T[i] = C[i] - '0';
    for (int i = 1; i <= n; i++) {
        if (!A[i]) continue;
        int j = i; 
        while (j <= n && A[j]) j++;
        st.insert({{i, j - 1}, 0});
        i = j - 1;
    }
    tmp = st;
    for (int i = 1; i <= q; i++) {
        string t; cin >> t;
        type[i] = (t == "toggle");
        if (type[i]) {
            scanf("%d", &ql[i]);
            if (A[ql[i]]) {
               __erase(ql[i]);
            } else {
               __add(ql[i]);
            }
            A[ql[i]] ^= 1;
        } else {
            scanf("%d%d", &ql[i], &qr[i]);
        }
    }
    for (int i = 0; i < N; i++) {
        vec[i].push_back(0);
        sort(vec[i].begin(), vec[i].end()); 
        vec[i].resize(unique(vec[i].begin(), vec[i].end()) - vec[i].begin());
        while (SZ(F[i]) < SZ(vec[i]) + 10) F[i].push_back(0);
    } 
    st = tmp;
    for (int i = 1; i <= n; i++) {
        A[i] = T[i];
    }
    for (int i = 1; i <= q; i++) {
        if (type[i]) {
            if (A[ql[i]]) erase(ql[i], i);
            else add(ql[i], i);
            A[ql[i]] ^= 1;
        } else {
            int x = get(ql[i], qr[i] - 1);
            auto it = st.upper_bound({{ql[i], MOD}, 0});
            if (it != st.begin()) {
                it--; 
                if (it->F.S >= qr[i] - 1) x += i - it->S;
            }
            printf("%d\n", x);
        }
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |     scanf("%d%d\n%s", &n, &q, C + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |             scanf("%d", &ql[i]);
      |             ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:125:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |             scanf("%d%d", &ql[i], &qr[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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