oj.uz

Submission #634644

# Submission time Handle Problem Language Result Execution time Memory
634644 2022-08-24T16:18:30 Z dutinmeow Street Lamps (APIO19_street_lamps) C++17
60 / 100
 5000 ms 243892 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

template<class Base>
class segment_tree : public Base {
    using T = typename Base::T;
    using Base::dval;
    using Base::merge;
    using Base::apply;
 
protected:
    size_t n;
 
    struct node {
        T v;
        int l, r;
        node() = default;
        node(T _v, int _l, int _r) : v(_v), l(_l), r(_r) {}
    };
 
    int root;
    std::vector<node> tree;
 
    size_t new_node() {
        tree.emplace_back(dval, -1, -1);
        return tree.size() - 1;
    }
 
private:
    void update(int i, T v, int t, int tl, int tr) {
        if (tl == tr) {
            apply(tree[t].v, v);
            return;
        }
 
        int tm = (tl + tr) / 2;
 
        if (i <= tm) {
            if (tree[t].l == -1)
                tree[t].l = new_node();
 
            update(i, v, tree[t].l, tl, tm);
        } else {
            if (tree[t].r == -1)
                tree[t].r = new_node();
 
            update(i, v, tree[t].r, tm + 1, tr);
        }
 
        tree[t].v = merge(tree[t].l == -1 ? dval : tree[tree[t].l].v, tree[t].r == -1 ? dval : tree[tree[t].r].v);
    }
 
    T query(int l, int r, int t, int tl, int tr) {
        if (r < tl || tr < l)
            return dval;
 
        if (l <= tl && tr <= r)
            return tree[t].v;
 
        int tm = (tl + tr) / 2;
        return merge(tree[t].l == -1 ? dval : query(l, r, tree[t].l, tl, tm), tree[t].r == -1 ? dval : query(l, r,
                     tree[t].r, tm + 1, tr));
    }
 
public:
    segment_tree() = default;
 
    segment_tree(size_t _n) {
        init(_n);
    }
 
    void init(size_t _n) {
        n = _n;
        root = new_node();
    }
 
    void reserve(size_t _n) {
        tree.reserve(_n);
    }
 
    void clear() {
        tree.clear();
    }
 
    void update(int i, T v) {
        update(i, v, root, 0, n - 1);
    }
 
    T query(int l, int r) {
        return query(l, r, root, 0, n - 1);
    }
};
 
struct segment_tree_template {
    using T = int;
    const T dval = 0;
    T merge(T a, T b) { return a + b; }
    void apply(T &a, T b) { a += b; }
};
 
class Fentree {
    size_t n;
    std::vector<segment_tree<segment_tree_template>> tree;
 
public:
    Fentree() = default;
 
    Fentree(size_t _n) {
        init(_n);
    }
 
    void init(size_t _n) {
        n = _n;
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++)
            tree[i].init(n);
    }
 
    void update(int i, int j, int v) {
        for (i++; i <= n; i += i & -i)
            tree[i].update(j, v);
    }
 
    int query(int i, int l, int r) {
        int ret = 0;
        for (i++; i; i -= i & -i)
            ret += tree[i].query(l, r);
        return ret;
    }
 
    int query(int i, int j, int l, int r) {
        return query(j, l, r) - query(i - 1, l, r);
    }
};
 
int main() {
	using namespace std;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

    int N, Q;
    string S;
    cin >> N >> Q >> S;
    set<int> off;
    Fentree bit(N + 1);
 
    for (int i = 0; i < N; i++) {
        if (S[i] == '0') {
            auto [it, b] = off.insert(i);
            int r = *it - 1;
            int l = (it == off.begin() ? 0 : *prev(it) + 1);
            // update [l, r] x [l, r]
            bit.update(l, l, Q);
            bit.update(r + 1, l, -Q);
            bit.update(l, r + 1, -Q);
            bit.update(r + 1, r + 1, Q);
        } else if (i == N - 1) {
            int r = N - 1;
            int l = (off.empty() ? 0 : *prev(off.end()) + 1);
            // update [l, r] x [l, r]
            bit.update(l, l, Q);
            bit.update(r + 1, l, -Q);
            bit.update(l, r + 1, -Q);
            bit.update(r + 1, r + 1, Q);
        }
    }
 
    for (int q = 1; q <= Q; q++) {
        string t;
        cin >> t;
 
        if (t == "query") {
            int l, r;
            cin >> l >> r;
            l--, r -= 2;
 
            if (off.lower_bound(l) == off.upper_bound(r)) {
                cout << bit.query(0, l, 0, r) - (Q - q) << '\n';
            } else {
                cout << bit.query(0, l, 0, r) << '\n';
            }
        } else if (t == "toggle") {
            int k;
            cin >> k;
            k--;
 
            if (S[k] == '0') {
                S[k] = '1';
                off.erase(k);
                auto itl = off.lower_bound(k);
                int l = (itl == off.begin() ? 0 : *prev(itl) + 1);
                auto itr = off.upper_bound(k);
                int r = (itr == off.end() ? N - 1 : *itr - 1);
                // update [l, k] x [k, r]
                bit.update(l, k, Q - q);
                bit.update(l, r + 1, q - Q);
                bit.update(k + 1, k, q - Q);
                bit.update(k + 1, r + 1, Q - q);
            } else {
                S[k] = '0';
                auto itl = off.lower_bound(k);
                int l = (itl == off.begin() ? 0 : *prev(itl) + 1);
                auto itr = off.upper_bound(k);
                int r = (itr == off.end() ? N - 1 : *itr - 1);
                off.insert(k);
                // update [l, k] x [k, r]
                bit.update(l, k, q - Q);
                bit.update(l, r + 1, Q - q);
                bit.update(k + 1, k, Q - q);
                bit.update(k + 1, r + 1, q - Q);
            }
        }
    }
}

Compilation message

street_lamps.cpp: In member function 'void Fentree::init(size_t)':
street_lamps.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for (int i = 1; i <= n; i++)
      |                         ~~^~~~
street_lamps.cpp: In member function 'void Fentree::update(int, int, int)':
street_lamps.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (i++; i <= n; i += i & -i)
      |                   ~~^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 1324 KB Output is correct
2 Correct 387 ms 1532 KB Output is correct
3 Correct 739 ms 5508 KB Output is correct
4 Correct 3480 ms 199388 KB Output is correct
5 Correct 2910 ms 197680 KB Output is correct
6 Correct 3531 ms 202512 KB Output is correct
7 Correct 2739 ms 219016 KB Output is correct
8 Correct 203 ms 26028 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 892 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Execution timed out 5074 ms 243892 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 1528 ms 180348 KB Output is correct
6 Correct 2454 ms 192608 KB Output is correct
7 Correct 3427 ms 201928 KB Output is correct
8 Correct 4571 ms 212228 KB Output is correct
9 Correct 440 ms 4172 KB Output is correct
10 Correct 337 ms 3328 KB Output is correct
11 Correct 454 ms 4276 KB Output is correct
12 Correct 339 ms 3448 KB Output is correct
13 Correct 421 ms 4176 KB Output is correct
14 Correct 350 ms 3332 KB Output is correct
15 Correct 2539 ms 225000 KB Output is correct
16 Correct 214 ms 31984 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 264 ms 1324 KB Output is correct
9 Correct 387 ms 1532 KB Output is correct
10 Correct 739 ms 5508 KB Output is correct
11 Correct 3480 ms 199388 KB Output is correct
12 Correct 2910 ms 197680 KB Output is correct
13 Correct 3531 ms 202512 KB Output is correct
14 Correct 2739 ms 219016 KB Output is correct
15 Correct 203 ms 26028 KB Output is correct
16 Correct 5 ms 892 KB Output is correct
17 Correct 4 ms 852 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Execution timed out 5074 ms 243892 KB Time limit exceeded
21 Halted 0 ms 0 KB -