Submission #173434

#	Time	Username	Problem	Language	Result	Execution time	Memory
173434		TAISA_	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	696 ms	15620 KiB

street_lamps

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
struct T {
    int a, b, c;
    bool operator<(const T &t) const { return a < t.a; }
};
int n, q;
vector<pair<T, int>> v;
vector<int> res;
struct BIT {
    vector<ll> dat;
    void build(int n) { dat.resize(++n); }
    void add(int k, int x) {
        for (++k; k < dat.size(); k += k & -k) {
            dat[k] += x;
        }
    }
    ll sum(int k) {
        ll res = 0;
        for (++k; k > 0; k -= k & -k) {
            res += dat[k];
        }
        return res;
    }
} bit;
void calc(int l, int r) {
    if (r - l <= 1) {
        return;
    }
    int mid = (l + r) / 2;
    vector<T> vs;
    vector<P> vq;
    for (int i = l; i < mid; i++) {
        if (v[i].second != -1) {
            vs.emplace_back(T{v[i].first.b, v[i].first.c, v[i].second});
        }
    }
    for (int i = mid; i < r; i++) {
        if (v[i].second == -1) {
            vq.emplace_back(v[i].first.b, v[i].first.c);
        }
    }
    sort(all(vs));
    reverse(all(vs));
    sort(all(vq));
    reverse(all(vq));
    int id = 0;
    for (int i = 0; i < vq.size(); i++) {
        while (id < vs.size() && vq[i].first <= vs[id].a) {
            bit.add(vs[id].b, vs[id].c);
            id++;
        }
        res[vq[i].second - 1] += bit.sum(vq[i].second);
    }
    for (int i = 0; i < id; i++) {
        bit.add(vs[i].b, -vs[i].c);
    }
    calc(l, mid);
    calc(mid, r);
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> q;
    string s;
    cin >> s;
    int b = -1;
    set<T> st;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            if (b == -1) {
                b = i;
            }
        } else {
            st.insert({b, i - 1, 0});
            b = -1;
        }
    }
    if (b != -1) {
        st.insert({b, n - 1, 0});
    }
    res.resize(q, -1);
    for (int i = 0; i < q; i++) {
        string t;
        cin >> t;
        int a, b;
        if (t == "toggle") {
            cin >> a;
            --a;
            if (s[a] == '1') {
                auto it = prev(st.lower_bound({a + 1, -1, -1}));
                T p1 = {(*it).a, a - 1, i + 1};
                T p2 = {a + 1, (*it).b, i + 1};
                v.emplace_back(T{(*it).a, (*it).b, i + 1}, i + 1 - (*it).c);
                st.erase(it);
                if (p1.a < a) {
                    st.insert(p1);
                }
                if (a < p2.b) {
                    st.insert(p2);
                }
            } else {
                auto ir = st.lower_bound({a + 1, -1, -1});
                auto il = prev(ir);
                T p = {a, a, i + 1};
                if (ir != st.end() && (*ir).a == a + 1) {
                    v.emplace_back(T{(*ir).a, (*ir).b, i + 1}, i + 1 - (*ir).c);
                    p.b = (*ir).b;
                    st.erase(ir);
                }
                if (ir != st.begin() && (*il).b == a - 1) {
                    v.emplace_back(T{(*il).a, (*il).b, i + 1}, i + 1 - (*ir).c);
                    p.a = (*il).a;
                    st.erase(il);
                }
                st.insert(p);
            }
        } else {
            cin >> a >> b;
            --a;
            --b;
            res[i] = 0;
            if (st.lower_bound({a + 1, -1, -1}) != st.begin()) {
                T it = *prev(st.lower_bound({a + 1, -1, -1}));
                if (it.b >= b - 1) {
                    res[i] += i + 1 - it.c;
                }
            }
            v.emplace_back(T{a + 1, b, i + 1}, -1);
        }
    }
    bit.build(q + 10);
    sort(all(v));
    calc(0, v.size());
    for (int i = 0; i < q; i++) {
        if (res[i] != -1) {
            cout << res[i] << endl;
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void BIT::add(int, int)':
street_lamps.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (++k; k < dat.size(); k += k & -k) {
                   ~~^~~~~~~~~~~~
street_lamps.cpp: In function 'void calc(int, int)':
street_lamps.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vq.size(); i++) {
                     ~~^~~~~~~~~~~
street_lamps.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (id < vs.size() && vq[i].first <= vs[id].a) {
                ~~~^~~~~~~~~~~

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