oj.uz

Submission #461248

# Submission time Handle Problem Language Result Execution time Memory
461248 2021-08-09T15:30:13 Z emuyumi Street Lamps (APIO19_street_lamps) C++17
60 / 100
 5000 ms 74492 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 = 5e5 + 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];
    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;
// cout << L << " " << R << '\n';
// cout.flush();
    int mid = (L + R) >> 1;
    ll tot = 0;
    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));
        }

    }
    vector<int> ql, qr;
    for (int idxs : qs){
        auto &[op, t, l, r] = points[idxs];

        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;
if (bad) return;
// cout << '\n';
// cout << L << " " << R << '\n';
    int mid = (L + R) >> 1;
    for (int i = L; i <= R; ++i) arr[i] = 0;
    points.clear();
    int last = 0;
    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;
// cout << " -> " << lower << " " << upper << '\n';
        points.push_back({1, t - last, lower, upper});
        last = t;
        
        if (op == 1){
            arr[l] ^= 1;
            st.set(l, arr[l]);
        }
        if (op == 2){
            if (l > mid || r < mid) continue;
// cout << t << " " << l << " " << r << '\n';
            points.push_back({2, t, l, r});
        }
    }
    vector<int> ql, qr;
    for (int idxs : qs){
        auto &[op, t, l, r] = queries[idxs];
        if (op == 1){
            if (l < mid) ql.push_back(idxs);
            if (l > mid) qr.push_back(idxs);
        }
        if (op == 2){
            if (r < mid) ql.push_back(idxs);
            if (l > mid) qr.push_back(idxs);
        }
    }

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

    for (int i = L - 1; i <= R + 1; ++i) st.set(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 5 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 4 ms 544 KB Output is correct
7 Correct 4 ms 588 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 22024 KB Output is correct
2 Correct 991 ms 22544 KB Output is correct
3 Correct 1829 ms 24624 KB Output is correct
4 Execution timed out 5040 ms 50772 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 588 KB Output is correct
2 Correct 8 ms 716 KB Output is correct
3 Correct 8 ms 716 KB Output is correct
4 Correct 11 ms 716 KB Output is correct
5 Correct 1393 ms 34288 KB Output is correct
6 Correct 1969 ms 35184 KB Output is correct
7 Correct 2325 ms 59668 KB Output is correct
8 Correct 3921 ms 74492 KB Output is correct
9 Correct 289 ms 24008 KB Output is correct
10 Correct 318 ms 25544 KB Output is correct
11 Correct 357 ms 27160 KB Output is correct
12 Correct 948 ms 48284 KB Output is correct
13 Correct 3848 ms 74312 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 8 ms 700 KB Output is correct
3 Correct 8 ms 716 KB Output is correct
4 Correct 6 ms 752 KB Output is correct
5 Correct 1662 ms 56036 KB Output is correct
6 Correct 2136 ms 63576 KB Output is correct
7 Correct 2236 ms 62040 KB Output is correct
8 Correct 1913 ms 59920 KB Output is correct
9 Correct 878 ms 23408 KB Output is correct
10 Correct 688 ms 23444 KB Output is correct
11 Correct 905 ms 26032 KB Output is correct
12 Correct 687 ms 23328 KB Output is correct
13 Correct 898 ms 25480 KB Output is correct
14 Correct 697 ms 23224 KB Output is correct
15 Correct 943 ms 47844 KB Output is correct
16 Correct 3868 ms 74412 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 4 ms 544 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 695 ms 22024 KB Output is correct
9 Correct 991 ms 22544 KB Output is correct
10 Correct 1829 ms 24624 KB Output is correct
11 Execution timed out 5040 ms 50772 KB Time limit exceeded
12 Halted 0 ms 0 KB -