Submission #985670

#	Time	Username	Problem	Language	Result	Execution time	Memory
985670		crafticat	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	1719 ms	524288 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;
constexpr int inf = 1e9;
int N;
int segSize;

struct Segment {
    Segment *left = nullptr, *right = nullptr;
    bool used = false;
    int l, r, mid;
    int val = 0, lazy = 0;

    Segment(int l, int r) : l(l), r(r), mid((r + l) / 2) {

    }

    void sparse() {
        if (used) return;
        used = true;
        if (r - l > 1) {
            left = new Segment(l,mid);
            right = new Segment(mid,r);
        }
    }

    void push() {
        if (lazy != 0) {
            val += (r - l) * lazy;
            if (r - l > 1) {
                left->lazy+=lazy;
                right->lazy+=lazy;
            }
            lazy = 0;
        }
    }

    int q(int a, int b) {
        sparse();
        push();
        if (a >= r || b <= l) return 0;
        if (a <= l && b >= r) return val;

        return left->q(a,b) + right->q(a,b);
    }
    void update(int a, int b, int v) {
        sparse();
        push();
        if (a >= r || b <= l) return;
        if (a <= l && b >= r) {
            lazy += v;
            push();
            return;
        }

        left->update(a,b,v);
        right->update(a,b,v);
        val = left->val + right->val;
    }

    void update(int x, int u) {
        sparse();
        push();
        if (r - l <= 1) {
            val += u;
            return;
        }

        if (x < mid)
            left->update(x,u);
        else
            right->update(x,u);

        val = left->val + right->val;
    }
    int getRight(int a, int b) {
        sparse();
        push();

        while (b > a) {
            int m = a + (b - a) / 2;
            if (q(m,b + 1) != b + 1 - m) {
                a = m + 1;
            } else
                b = m;
        }
        return a;
    }
    int getLeft(int a, int b) {
        sparse();
        push();

        while (b > a) {
            int m = a + (b - a) / 2;
            if (q(a,m + 1) != m + 1 - a) {
                b = m;
            } else
                a = m + 1;
        }
        return a;
    }
};

struct Segment2D {
    Segment2D *left = nullptr, *right = nullptr;
    int l, r, mid;
    bool used = false;
    Segment *val, *sum;

    Segment2D(int l, int r) : l(l), r(r), mid((l + r) / 2) {
        val = new Segment(0,segSize);
        sum = new Segment(0,segSize);
    }
    void sparse() {
        if (used) return;
        used = true;
        if (r - l > 1) {
            left = new Segment2D(l,mid);
            right = new Segment2D(mid,r);
        }
    }

    int q(int a, int b, int aL, int aR) {
        sparse();
        if (a >= r || b <= l) return 0;
        if (a <= l && b >= r) return val->q(aL,aR) + sum->q(aL,aR);

        int res = val->q(aL,aR);
        return res + left->q(a,b,aL,aR) + right->q(a,b,aL,aR);
    }

    void update(int a, int b, int aL,int aR, int v) {
        sparse();
        if (a >= r || b <= l) return;
        if (a <= l && b >= r) {
            val->update(aL,aR,v);
            return;
        }

        left->update(a,b,aL,aR,v);
        right->update(a,b,aL,aR,v);
        sum->update(aL,aR,v);
    }
};

Segment *checkSeg;
set<int> zeroes;
set<int> zeroesRev;
pair<int,int> getRanges(int i) {
    auto it = zeroes.lower_bound(i);
    int r;
    if (it == zeroes.end()) r = N - 1;
    else r = *it - 1;
    auto it2 = zeroesRev.lower_bound(-i);
    int l;
    if (it2 == zeroesRev.end()) l = 0;
    else l = -*it2 + 1;
    return {l,r};
}

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

    int n, q; cin >> n>> q;
    N = n;
    string s; cin >> s;
    vector<int> time(n,0);
    checkSeg = new Segment(0,n);

    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '1') checkSeg->update(i,1);
        else {
            zeroes.insert(i);
            zeroesRev.insert(-i);
        }
    }

    // Insert A (l, r)
    // Erase A, (l, r)
    // Check b, a (l, r)

    vector<tuple<int,int,int,int,int>> queries; // A,1, 1, (l, r) (insert)
    vector<bool> qAsk(q);
    // B, 3, a (l, r)
    // B -1, 2, a (l, r)

    for (int i = 0; i < q; ++i) {
        string type; cin >> type;
        qAsk[i] = type == "query";
        if (type == "toggle") {
            int x; cin >> x;
            x--;

            if (s[x] == '1') {
                auto [l, r] = getRanges(x);
                int t = time[l];
                queries.emplace_back(l,1,1,t,i + 1);
                queries.emplace_back(r,3,l,t,i + 1);
                checkSeg->update(x,-1);
                if (s[l] == '1') time[l] = i + 1;
                if (x + 1 < n && s[x + 1] == '1') time[x + 1] = i + 1;
            } else {
                if ( x - 1 >= 0 && s[x - 1] == '1') {
                    auto [l, r] = getRanges(x - 1);
                    int t = time[l];
                    queries.emplace_back(l,1,1,t,i + 1);
                    queries.emplace_back(r,3,l,t,i + 1);
                    time[l] = i + 1;
                }
                if (x + 1 < n && s[x + 1] == '1') {
                    auto [l, r] = getRanges(x + 1);
                    int t = time[l];
                    queries.emplace_back(l,1,1,t,i + 1);
                    queries.emplace_back(r,3,l,t,i + 1);
                    time[l] = i + 1;
                }

                checkSeg->update(x,1);
                if (s[x] == '0') {
                    zeroes.erase(x);
                    zeroesRev.erase(-x);
                }
                if (s[x] == '1') {
                    zeroes.insert(x);
                    zeroesRev.insert(-x);
                }
                auto [l, r] = getRanges(x);
                time[l] = i + 1;
            }
            if (s[x] == '0') {
                zeroes.erase(x);
                zeroesRev.erase(-x);
            }
            s[x] = s[x] == '1' ? '0' : '1';
            if (s[x] == '0') {
                zeroes.insert(x);
                zeroesRev.insert(-x);
            }
        } else {
            int a, b; cin >> a >> b;
            a--;
            b--;
            b--;
            queries.emplace_back(b,2,a,0,i + 1);
        }
    }
    for (int x = 0; x < n; ++x) {
        if (s[x] == '1') {
            auto [l, r] = getRanges(x);
            int t = time[l];
            if (t == q) continue;
            queries.emplace_back(l,1,1,t,q);
            queries.emplace_back(r,3,l,t,q);
            checkSeg->update(l,r,0);
            time[l] = q;
        }
    }

    std::sort(queries.begin(), queries.end());
    segSize = q;
    Segment2D seg(-1,N);
    vector<int> ans(q);
    int global = 0;

    for (auto [a, t, b, l, r] : queries) {
        if (t == 1) {
            // Create
            seg.update(a,inf,l,r,1);
            global+=r - l;
        }
        if (t == 2) {
            ans[r - 1] = seg.q(b,b+1,l,r);
        }
        if (t == 3) {
            seg.update(b,inf,l,r,-1);
            global-= r - l;
        }
    }

    for (int i = 0; i < q; ++i) {
        if (qAsk[i]) cout << ans[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:170:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     for (int i = 0; i < s.size(); ++i) {
      |                     ~~^~~~~~~~~~

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