Submission #539309

#	Time	Username	Problem	Language	Result	Execution time	Memory
539309		SlavicG	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	175 ms	13148 KiB

foehn_phenomena

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

#define int long long
template<typename T, bool zero_indexing>
struct fenwick_tree {
    int N;
    vector<T> fen;
    fenwick_tree(int n) {
        N = n, fen.assign(n + 1, 0);
    }
    fenwick_tree(vector<T> a) {
        N = a.size();
        fen.assign(N + 1, 0);
        for(int i = 0; i < N; ++i) {
            add(i, a[i]);
        }
    }
    void add(int p, T val) {
        for(int i = p + zero_indexing;i <= N;i += i & -i) {
            fen[i] += val;
        }
    }
    void set(int p, T val) {
        T set_val = val - query(p, p);
        add(p, set_val);
    }

    T query(int l, int r) {
        T ret = 0;
        for(int i = r + zero_indexing; i >= 1; i -= i & -i) {
            ret += fen[i];
        }   
        for(int i = l + zero_indexing - 1; i >= 1; i -= i & -i) {
            ret -= fen[i];
        }   
        return ret;
    }
};

ll gett(int a, int b) {return a + b;}
ll upp(int a, int b) {return a + b;}
void solve() {
    int n, q, s, t;
    cin >> n >> q >> s >> t; ++n;

    vector<int> a(n);
    fenwick_tree<ll, 1> st(n + 2);
        

    for(int i = 0;i < n; ++i) {
        cin >> a[i];
        st.add(i, a[i]);
        st.add(i + 1, -a[i]);
    }
    ll ans = 0;
    for(int i = 0; i + 1 < n; ++i) {
        if(a[i] < a[i + 1]) {
            ans -= abs(a[i + 1] - a[i]) * s;
        } else {
            ans += abs(a[i] - a[i + 1]) * t;
        }
    }

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

        ll prev = st.query(0, l - 1);
        ll now = st.query(0, l), next;
        if(prev < now) ans += abs(now - prev) * s;
        else ans -= abs(now - prev) * t;

        if(r + 1 < n) {
            now = st.query(0, r);
            next = st.query(0, r + 1);
            if(now < next)ans += abs(next - now) * s; 
            else ans -= abs(now - next) * t;
        }
        st.add(l, x);
        st.add(r + 1, -x);
        prev = st.query(0, l - 1);
        now = st.query(0, l);

        if(prev < now) ans -= abs(now - prev) * s;
        else ans += abs(prev - now) * t;

        if(r + 1 < n) {
            now = st.query(0, r);
            next = st.query(0, r + 1);
            if(now < next)ans -= abs(next - now) * s; 
            else ans += abs(now - next) * t;
        }

        cout << ans << "\n";

    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

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