oj.uz

Submission #461256

# Submission time Handle Problem Language Result Execution time Memory
461256 2021-08-09T15:53:03 Z emuyumi Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4548 ms 71136 KB 
#include <bits/stdc++.h>

using namespace std;
#define ms(x, a) memset(x, a, sizeof x)
typedef long long ll;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f;
const int MN = 3e5 + 10;

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder
namespace{
    using S = bool;
    S op(S a, S b){ return (a & b ? 1 : 0); }
    S e(){ return 1; }
    bool f(bool x){ return x; }
}
atcoder::segtree<S, op, e> st(MN + 10);
struct Fenwick{
    int a[MN], T = 0, hist[MN * 2];
    void upd(int i, int val){ hist[++T] = i; for (++i; i < MN; i += i & -i) a[i] += val; }
    void remove(int i){ for (++i; i < MN; i += i & -i) a[i] = 0; }
    int qry(int i){ int ret = 0; for (++i; i; i -= i & -i) ret += a[i]; return ret; }
    int qry(int l, int r){ return qry(r) - qry(l - 1); }
    void reset(){
        for (int i = 1; i <= T; ++i) remove(hist[i]);
        T = 0;
    }
} bit;
int N, Q, ans[MN]; bool arr[MN];
struct Query{ int op, t, l, r; };
vector<Query> queries, points;

void cdq2(vector<int> &qs, int L, int R){
    if (qs.empty() || L > R) return;

    bool bad = 1;
    for (int idxs : qs) if (points[idxs].op == 2){ bad = 0; break; }
    if (bad) return;

    int mid = (L + R) >> 1;
    ll tot = 0;
    vector<int> ql, qr;

    for (int idxs : qs){
        auto &[op, t, l, r] = points[idxs];

        if (op == 1){
            if (l <= mid) bit.upd(r, t), tot += t;
        }
        if (op == 2){
            if (l >= mid) ans[t] += (tot - bit.qry(r - 1));
        }

        if (l < mid) ql.push_back(idxs);
        if (l > mid) qr.push_back(idxs);
    }

    bit.reset();
    cdq2(ql, L, mid - 1), cdq2(qr, mid + 1, R);
}

void cdq1(vector<int> &qs, int L, int R){
    if (qs.empty() || L > R) return;

    bool bad = 1;
    for (int idxs : qs) if (queries[idxs].op == 2){ bad = 0; break; }
    if (bad) return;

    int mid = (L + R) >> 1;
    vector<int> ql, qr;
    int last = 0;
    points.clear();

    for (int idxs : qs){
        auto &[op, t, l, r] = queries[idxs];
        
        int lower = st.min_left<f>(mid + 1);
        int upper = st.max_right<f>(mid) - 1;
        lower = max(lower, L), upper = min(upper, R);
        points.push_back({1, t - last, lower, upper});
        last = t;
        
        if (op == 1){
            arr[l] ^= 1;
            st.set(l, arr[l]);
            
            if (l < mid) ql.push_back(idxs);
            if (l > mid) qr.push_back(idxs);
        }
        if (op == 2){
            if (l > mid) qr.push_back(idxs);
            else if (r < mid) ql.push_back(idxs);
            else points.push_back({2, t, l, r});
        }
    }

    vector<int> qs2(points.size());
    iota(qs2.begin(), qs2.end(), 0);
    cdq2(qs2, 1, N);

    for (int i = L - 1; i <= R + 1; ++i){
        if (arr[i]) st.set(i, 0), arr[i] = 0;
    }
    cdq1(ql, L, mid - 1), cdq1(qr, mid + 1, R);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> Q;
    for (int i = 1; i <= N; ++i){
        char c; cin >> c;
        st.set(i, 0);
        if (c == '1') queries.push_back({1, 0, i});   
    }
    st.set(0, 0), st.set(N + 1, 0);
    for (int i = 1; i <= Q; ++i){
        string s; cin >> s;
        if (s == "toggle"){
            int l; cin >> l;
            queries.push_back({1, i, l});
        }
        if (s == "query"){
            int l, r; cin >> l >> r; r--;
            queries.push_back({2, i, l, r});
        }
    }
    vector<int> qs(queries.size());
    iota(qs.begin(), qs.end(), 0);
    cdq1(qs, 1, N);
// cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << '\n';
    for (auto &[op, t, l, r] : queries){
        if (op == 2){
// cout << "query " << l << " " << r + 1 << ":       ";
            cout << ans[t] << '\n';
        }
    }
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 21104 KB Output is correct
2 Correct 622 ms 22100 KB Output is correct
3 Correct 1098 ms 22168 KB Output is correct
4 Correct 2184 ms 29128 KB Output is correct
5 Correct 2809 ms 36096 KB Output is correct
6 Correct 2005 ms 33400 KB Output is correct
7 Correct 1692 ms 28840 KB Output is correct
8 Correct 4548 ms 50332 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 588 KB Output is correct
2 Correct 6 ms 588 KB Output is correct
3 Correct 6 ms 588 KB Output is correct
4 Correct 8 ms 716 KB Output is correct
5 Correct 761 ms 30460 KB Output is correct
6 Correct 1173 ms 32040 KB Output is correct
7 Correct 1423 ms 54816 KB Output is correct
8 Correct 2559 ms 70896 KB Output is correct
9 Correct 249 ms 21012 KB Output is correct
10 Correct 251 ms 22864 KB Output is correct
11 Correct 325 ms 24872 KB Output is correct
12 Correct 416 ms 24832 KB Output is correct
13 Correct 2603 ms 71136 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 716 KB Output is correct
2 Correct 6 ms 664 KB Output is correct
3 Correct 7 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 932 ms 56932 KB Output is correct
6 Correct 937 ms 38320 KB Output is correct
7 Correct 985 ms 35532 KB Output is correct
8 Correct 749 ms 29808 KB Output is correct
9 Correct 612 ms 21196 KB Output is correct
10 Correct 518 ms 19880 KB Output is correct
11 Correct 629 ms 20904 KB Output is correct
12 Correct 510 ms 20000 KB Output is correct
13 Correct 609 ms 20900 KB Output is correct
14 Correct 513 ms 19988 KB Output is correct
15 Correct 403 ms 24804 KB Output is correct
16 Correct 2596 ms 71072 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 472 ms 21104 KB Output is correct
9 Correct 622 ms 22100 KB Output is correct
10 Correct 1098 ms 22168 KB Output is correct
11 Correct 2184 ms 29128 KB Output is correct
12 Correct 2809 ms 36096 KB Output is correct
13 Correct 2005 ms 33400 KB Output is correct
14 Correct 1692 ms 28840 KB Output is correct
15 Correct 4548 ms 50332 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 6 ms 588 KB Output is correct
18 Correct 6 ms 588 KB Output is correct
19 Correct 8 ms 716 KB Output is correct
20 Correct 761 ms 30460 KB Output is correct
21 Correct 1173 ms 32040 KB Output is correct
22 Correct 1423 ms 54816 KB Output is correct
23 Correct 2559 ms 70896 KB Output is correct
24 Correct 249 ms 21012 KB Output is correct
25 Correct 251 ms 22864 KB Output is correct
26 Correct 325 ms 24872 KB Output is correct
27 Correct 416 ms 24832 KB Output is correct
28 Correct 2603 ms 71136 KB Output is correct
29 Correct 7 ms 716 KB Output is correct
30 Correct 6 ms 664 KB Output is correct
31 Correct 7 ms 588 KB Output is correct
32 Correct 4 ms 588 KB Output is correct
33 Correct 932 ms 56932 KB Output is correct
34 Correct 937 ms 38320 KB Output is correct
35 Correct 985 ms 35532 KB Output is correct
36 Correct 749 ms 29808 KB Output is correct
37 Correct 612 ms 21196 KB Output is correct
38 Correct 518 ms 19880 KB Output is correct
39 Correct 629 ms 20904 KB Output is correct
40 Correct 510 ms 20000 KB Output is correct
41 Correct 609 ms 20900 KB Output is correct
42 Correct 513 ms 19988 KB Output is correct
43 Correct 403 ms 24804 KB Output is correct
44 Correct 2596 ms 71072 KB Output is correct
45 Correct 143 ms 15532 KB Output is correct
46 Correct 256 ms 16276 KB Output is correct
47 Correct 508 ms 24152 KB Output is correct
48 Correct 990 ms 42308 KB Output is correct
49 Correct 202 ms 27564 KB Output is correct
50 Correct 213 ms 29728 KB Output is correct
51 Correct 240 ms 33824 KB Output is correct
52 Correct 228 ms 28588 KB Output is correct
53 Correct 188 ms 27708 KB Output is correct
54 Correct 248 ms 28620 KB Output is correct