Submission #1031681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031681		caterpillow	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2798 ms	475328 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

namespace treap {
    using ptr = struct Node*;
    struct Node {
        ptr l, r;
        int i;
        ll val, lazy;
        int lo, hi;

        Node(int i, ptr l, ptr r) : i(i), l(l), r(r), lo(i), hi(i) {
            val = lazy = 0;
            if (l) lo = l->lo;
            if (r) hi = r->hi;
        }
    };

    void inc(ptr n, int lo, int hi, ll v) {
        if (!n) return;
        if (lo > n->hi || hi < n->lo) return;
        if (lo <= n->lo && n->hi <= hi) {
            n->lazy += v;
            return;
        }
        if (lo <= n->i && n->i <= hi) n->val += v;
        inc(n->l, lo, hi, v);
        inc(n->r, lo, hi, v);
    }

    ll query(ptr n, int i) {
        if (n->i == i) return n->val + n->lazy;
        if (i <= n->i) return n->lazy + query(n->l, i);
        else return n->lazy + query(n->r, i);
    }

    ptr build(vt<int>& a, int l, int r) {
        if (l > r) return 0;
        int m = (l + r) / 2;
        return new Node(a[m], build(a, l, m - 1), build(a, m + 1, r));
    }
}

struct SegTree {
    int n;
    vt<vt<int>> todo;
    vt<treap::ptr> seg;
    void init(int _n) {
        for (n = 1; n < _n; n *= 2);
        todo.resize(2 * n);
        seg.resize(2 * n);
    }
    void load(int l, int r) {
        todo[l += n].pb(r);
        while (l /= 2) todo[l].pb(r);
    }
    void build() {
        FOR (i, 1, 2 * n) {
            seg[i] = treap::build(todo[i], 0, size(todo[i]) - 1);
        }
    }
    void upd(int l1, int l2, int r1, int r2, int v) {
        for (l1 += n, l2 += n + 1; l1 < l2; l1 /= 2, l2 /= 2) {
            if (l1 & 1) treap::inc(seg[l1++], r1, r2, v);
            if (l2 & 1) treap::inc(seg[--l2], r1, r2, v);
        }
    } 
    ll query(int l, int r) {
        ll res = treap::query(seg[l += n], r);
        while (l /= 2) res += treap::query(seg[l], r);
        return res;
    }
};

struct BIT {
    int n; vt<ll> arr;
    void init(int _n) {
        n = _n;
        arr.resize(n);
    }
    ll sum(int r) {
        ll s = 0;
        while (r) {
            s += arr[r - 1];
            r -= r & -r;
        }
        return s;
    }
    void add(int p, ll x) {
        for (++p; p <= n; p += p & -p) arr[p - 1] += x;
    }
    ll sum(int l, int r) {
        return sum(r + 1) - sum(l);
    }
};

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, q; cin >> n >> q;
    vt<int> state(n);
    BIT bit;
    bit.init(n);
    F0R (i, n) {
        char c; cin >> c;
        state[i] = (c == '1');
    }

    set<int> dead {-1, n};

    vt<pi> queries(q);
    vt<pi> pts;
    
    F0R (i, q) {
        string t; cin >> t;
        if (t == "query") {
            int l, r; cin >> l >> r; l--, r--;
            queries[i] = {l, r - 1};
            pts.pb({r - 1, l});
        } else if (t == "toggle") {
            int j; cin >> j;
            queries[i] = {j - 1, -1};
        } else assert(0);
    }

    sort(all(pts));
    pts.erase(unique(all(pts)), pts.end());

    SegTree seg; 
    seg.init(n);
    for (auto [r, l] : pts) seg.load(l, r);
    seg.build();

    auto enable = [&] (int i, int t) {
        state[i] = true;
        dead.erase(i);
        bit.add(i, 1);
        if (t) {
            auto it = dead.lower_bound(i);
            int nxt = *it, prv = *prev(it);
            seg.upd(prv + 1, i, i, nxt - 1, -t);
        }
    };

    auto disable = [&] (int i, int t) {
        if (t) bit.add(i, -1);
        auto it = dead.lower_bound(i);
        int nxt = *it;
        int prv = *prev(it);
        seg.upd(prv + 1, i, i, nxt - 1, t);
        state[i] = false;
        dead.insert(i);
    };

    F0R (i, n) {
        if (state[i]) enable(i, 0);
        else disable(i, 0);
    }

    int t = 0;
    for (auto [x, y] : queries) {
        t++;
        if (y == -1) {
            if (state[x] == 0) {
                enable(x, t);
            } else {
                disable(x, t);
            }
        } else {
            if (bit.sum(x, y) == y - x + 1) {
                cout << seg.query(x, y) + t << endl;
            } else {
                cout << seg.query(x, y) << endl;
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In constructor 'treap::Node::Node(int, treap::ptr, treap::ptr)':
street_lamps.cpp:29:13: warning: 'treap::Node::i' will be initialized after [-Wreorder]
   29 |         int i;
      |             ^
street_lamps.cpp:28:13: warning:   'treap::Node* treap::Node::l' [-Wreorder]
   28 |         ptr l, r;
      |             ^
street_lamps.cpp:33:9: warning:   when initialized here [-Wreorder]
   33 |         Node(int i, ptr l, ptr r) : i(i), l(l), r(r), lo(i), hi(i) {
      |         ^~~~
street_lamps.cpp: At global scope:
street_lamps.cpp:118:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  118 | main() {
      | ^~~~

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