Submission #835473

#	Time	Username	Problem	Language	Result	Execution time	Memory
835473		Koyote	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	185 ms	15272 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;

template<class T> void read(T &u) { cin >> u; }
template<class T, class... U> void read(T &u, U &...v) { read(u); read(v...); }

template <class S, S (*op)(S, S), S (*e)(),
          class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = lazy_segtree<S, op, e, F, mapping, composition, id>::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        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;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size, r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        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() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size, r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1, r >>= 1;
            }
            l = l2, r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

  private:
    static int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

const int N = 2e5 + 2;
int n, q, s, t;
vector<int64_t> a;

int64_t op(int64_t x, int64_t y) { return x ^ y; }
int64_t e() { return 0; }
struct F { int delta; };
int64_t mapping(F x, int64_t y) { return y + x.delta; }
F composition(F x, F y) { return F{x.delta + y.delta}; }
F id() { return F{0}; }

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    read(n, q, s, t); a.resize(n + 1);
    for (int64_t &i : a) read(i);
    lazy_segtree<int64_t, op, e, F, mapping, composition, id> b(a);

    int64_t val = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < a[i + 1]) val -= s * (a[i + 1] - a[i]);
        else val += t * (a[i] - a[i + 1]);
    }
    while (q--) {
        int l, r, x; read(l, r, x);
        
        {
            int Lvalue = b.get(l), Lvalue_before = b.get(l - 1);
            if (Lvalue_before < Lvalue) val += s * (Lvalue - Lvalue_before);
            else val -= t * (Lvalue_before - Lvalue);

            if (Lvalue_before < (x + Lvalue)) val -= s * ((x + Lvalue) - Lvalue_before);
            else val += t * (Lvalue_before - (x + Lvalue));
        }

        if (r < n) {
            int Rvalue = b.get(r), Rvalue_after = b.get(r + 1);
            if (Rvalue < Rvalue_after) val += s * (Rvalue_after - Rvalue);
            else val -= t * (Rvalue - Rvalue_after);

            if ((Rvalue + x) < Rvalue_after) val -= s * (Rvalue_after - (Rvalue + x));
            else val += t * ((Rvalue + x) - Rvalue_after);
        }

        cout << val << '\n';
        b.apply(l, r + 1, F{x});
    }
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 10
• Subtask 3: 0 / 60