제출 #1166794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166794		LucasLe	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	262 ms	13868 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define i64 long long

template<typename T>
bool minimize(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool maximize(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int MOD = 998244353;

template<typename T>
void add(T &x, T y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

template<typename T>
T bin_pow(T x, T y) {
    T res = 1;
    if (y < 0) return 1;
    while (y) {
        if (y & 1) res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}

const int maxn = 2e5 + 5;

int n, q, s, t;
long long a[maxn + 5];

struct segment_tree {
    long long t[4 * maxn + 5];
    long long lazy[4 * maxn + 5];
    void build(int id, int l, int r) {
        if (l == r) {
            t[id] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
    void push(int id, int l, int r) {
        t[id] += lazy[id];
        if (l != r) {
            lazy[id << 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];
        }
        lazy[id] = 0;
    }
    void update(int id, int l, int r, int lb, int rb, int x) {
        push(id, l, r);
        if (lb <= l && r <= rb) {
            lazy[id] += x;
            push(id, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        if (lb <= mid) 
            update(id << 1, l, mid, lb, rb, x);
        if (rb >= mid + 1)
            update(id << 1 | 1, mid + 1, r, lb, rb, x);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
    long long query(int id, int l, int r, int pos) {
        push(id, l, r);
        if (l == r) {
            return t[id];
        }
        int mid = (l + r) >> 1;
        long long a = 0, b = 0;
        if (pos <= mid)
            a = query(id << 1, l, mid, pos);
        if (pos > mid)
            b = query(id << 1 | 1, mid + 1, r, pos);
        return a + b;
    }
    void update(int l, int r, int x) {
        update(1, 1, n, l, r, x);
    }
    long long query(int pos) {
        return query(1, 1, n, pos);
    }
};

segment_tree seg;

void solve() {
    std::cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; ++i) std::cin >> a[i];
    
    seg.build(1, 1, n);

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        long long diff = a[i] - a[i - 1];
        if (diff > 0) {
            ans -= diff * s;
        } else {
            diff = -diff;
            ans += diff * t;
        }
    }

    while (q--) {
        int l, r, x; std::cin >> l >> r >> x;

        if (l - 1 > 0) a[l - 1] = seg.query(l - 1);
        if (r + 1 <= n) a[r + 1] = seg.query(r + 1);

        a[l] = seg.query(l);
        a[r] = seg.query(r);

        {
            long long diff = a[l] - a[l - 1];
            if (diff > 0) {
                ans += diff * s;
            } else {
                diff = -diff;
                ans -= diff * t;
            }
        }

        if (r + 1 <= n) {
            long long diff = a[r + 1] - a[r];
            if (diff > 0) {
                ans += diff * s;
            } else {
                diff = -diff;
                ans -= diff * t;
            }
        }

        seg.update(l, r, x);
        a[l] = seg.query(l);
        a[r] = seg.query(r);

        {
            long long diff = a[l] - a[l - 1];
            if (diff > 0) {
                ans -= diff * s;
            } else {
                diff = -diff;
                ans += diff * t;
            }
        }

        if (r + 1 <= n) {
            long long diff = a[r + 1] - a[r];
            if (diff > 0) {
                ans -= diff * s;
            } else {
                diff = -diff;
                ans += diff * t;
            }
        }

        std::cout << ans << '\n';
    }
}

int main() {

    // std::freopen("input.txt", "r", stdin);
//     std::freopen("KHOANG.inp", "r", stdin);
//     std::freopen("KHOANG.out", "w", stdout);

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    clock_t start = clock();

    int tc = 1;
//    std::cin >> tc;
    while (tc--)
        solve();

    std::cerr << "Time elapsed: " << clock() - start << " ms\n";
}

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