Submission #1276556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276556		bbldrizzy	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	5094 ms	4408 KiB

street_lamps

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
#include <limits>
#include <random>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define f first
#define s second
const int MOD = 1e9+7;
const ll inf = 4*1e18;
const int mx = 5*1e5+5;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

template<typename T> struct SegTreeMax {
    int n;
    vector<T> st;
    vector<T> lazy;
    vector<char> has_lazy;
    T ID;       // identity for query (very small)
    T init_val; // value used to initialize all elements

    // default init_val is numeric max so you can do SegTreeMax<ll> st(n);
    SegTreeMax(int _n = 0, T _init_val = numeric_limits<T>::max()) {
        init(_n, _init_val);
    }

    // initialize or re-initialize with chosen init_val
    void init(int _n, T _init_val = numeric_limits<T>::max()) {
        n = _n;
        init_val = _init_val;
        ID = numeric_limits<T>::lowest();
        if (n <= 0) {
            st.clear(); lazy.clear(); has_lazy.clear();
            return;
        }
        st.assign(4 * n, init_val); // <- fill tree with your desired "max" value
        lazy.assign(4 * n, T());
        has_lazy.assign(4 * n, 0);
    }

    // build from 0-indexed array a (overrides init_val length if sizes differ)
    void build(const vector<T>& a) {
        if ((int)a.size() != n) init((int)a.size(), init_val);
        build(1, 0, n - 1, a);
    }

    // set range [l, r] to val
    void range_set(int l, int r, T val) {
        if (n == 0 || l > r) return;
        range_set(1, 0, n - 1, l, r, val);
    }

    // query max on [l, r]
    T query(int l, int r) {
        if (n == 0 || l > r) return ID;
        return query(1, 0, n - 1, l, r);
    }

private:
    void apply_set(int v, int tl, int tr, T val) {
        st[v] = val;
        lazy[v] = val;
        has_lazy[v] = 1;
    }

    void push(int v, int tl, int tr) {
        if (!has_lazy[v] || tl == tr) return;
        int tm = (tl + tr) >> 1;
        apply_set(v<<1, tl, tm, lazy[v]);
        apply_set(v<<1|1, tm+1, tr, lazy[v]);
        has_lazy[v] = 0;
    }

    void build(int v, int tl, int tr, const vector<T>& a) {
        has_lazy[v] = 0;
        if (tl == tr) {
            st[v] = a[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build(v<<1, tl, tm, a);
        build(v<<1|1, tm+1, tr, a);
        st[v] = max(st[v<<1], st[v<<1|1]);
    }

    void range_set(int v, int tl, int tr, int l, int r, T val) {
        if (l > r) return;
        if (l == tl && r == tr) {
            apply_set(v, tl, tr, val);
            return;
        }
        push(v, tl, tr);
        int tm = (tl + tr) >> 1;
        if (r <= tm) range_set(v<<1, tl, tm, l, r, val);
        else if (l > tm) range_set(v<<1|1, tm+1, tr, l, r, val);
        else {
            range_set(v<<1, tl, tm, l, tm, val);
            range_set(v<<1|1, tm+1, tr, tm+1, r, val);
        }
        st[v] = max(st[v<<1], st[v<<1|1]);
    }

    T query(int v, int tl, int tr, int l, int r) {
        if (l > r) return ID;
        if (l == tl && r == tr) return st[v];
        push(v, tl, tr);
        int tm = (tl + tr) >> 1;
        return max(
            query(v<<1, tl, tm, l, min(r, tm)),
            query(v<<1|1, tm+1, tr, max(l, tm+1), r)
        );
    }
};

template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;

  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}

	/** Sets the value at index ind to val. */
	void set(int ind, T val) { add(ind, val - arr[ind]); }

	/** Adds val to the element at index ind. */
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}

	/** @return The sum of all values in [0, ind]. */
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};

int main() {
    int n, q; cin >> n >> q;
    string s1; cin >> s1;
    BIT<ll> ft1(n);
    BIT<ll> ft2(n);
    SegTreeMax<ll> seg(n);
    set<pair<ll, ll>> st;
    int str = -1;
    int en = -1;
    for (int i = 0; i < n; i++) {
        if (s1[i] - '0' == 0) {
            if (str != -1) {
                st.insert({str, en});
            }
            str = -1; 
        } else {
            seg.range_set(i, i, 0);
            if (str == -1) str = i;
            en = i;
            if (i == n-1) {
                st.insert({str, en});
            }
        }
    }
    // cout << seg.query(0, 1);
    // cout << "\n";
    // for (auto it: st) {
    //     cout << it.f << ", " << it.s << '\n';
    // }
    for (int i = 1; i <= q; i++) {
        string S; cin >> S;
        if (S == "query") {
            int a, b; cin >> a >> b; --a; b -= 2;
            ll x = seg.query(a, b);
            ll ans = 0;
            if (x != numeric_limits<ll>::max()) {
                ans += i-x;
            }
            ans += ft1.pref_sum(a);
            ans += ft2.pref_sum(n-1-b);
            ans -= ft1.pref_sum(n-1);
            cout << ans << "\n";
        } else {
            int x; cin >> x; --x;
            if (s1[x] == '0') {
                seg.range_set(x, x, i);
                int l = x; int r = x;
                auto it1 = st.upper_bound({x, 0});
                auto it2 = it1;
                bool one = false; bool two = false;
                if (it1 != st.end() && (*it1).f == x+1) {
                    one = true;
                    r = (*it1).s;
                    int vl = seg.query((*it1).f, (*it2).s);
                    ft1.add((*it1).f, i-vl);
                    ft2.add(n-1-(*it1).s, i-vl);
                    seg.range_set((*it1).f, (*it2).s, i);
                }
                if (it2 != st.begin()) {
                    it2--;
                    if ((*it2).s == x-1) {
                        l = (*it2).f;
                        two = true;
                        int vl = seg.query((*it2).f, (*it2).s);
                        ft1.add((*it2).f, i-vl);
                        ft2.add(n-1-(*it2).s, i-vl);
                        seg.range_set((*it2).f, (*it2).s, i);
                    }
                }
                if (one) st.erase(it1);
                if (two) st.erase(it2);
                st.insert({l, r});
            } else {
                auto it1 = st.upper_bound({x, 0});
                if (it1 != st.begin()) {
                    it1--;
                    int l1 = 1; int r1 = 0; int l2 = 1; int r2 = 0;
                    if (x >= (*it1).f && x <= (*it1).s) {
                        l1 = (*it1).f; r1 = x-1;
                        l2 = x+1; r2 = (*it1).s;
                        st.erase(it1);
                        ll v = seg.query(l1, r2);
                        ft1.add(l1, i-v);
                        ft2.add(n-1-l2, i-v);
                        if (l1 <= r1) {
                            st.insert({l1, r1});
                            seg.range_set(l1, r1, i);
                        }
                        if (l2 <= r2) {
                            st.insert({l2, r2});
                            seg.range_set(l2, r2, i);
                        }
                    } else {
                        st.erase(it1);
                        l1 = x; l2 = x;
                        ll v = seg.query(l1, r2);
                        ft1.add(l1, i-v);
                        ft2.add(n-1-l2, i-v);
                    }
                    seg.range_set(x, x, numeric_limits<ll>::max());
                }
            }
        }
    }
}

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