Submission #539210

#	Time	Username	Problem	Language	Result	Execution time	Memory
539210		timreizin	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	155 ms	14636 KiB

foehn_phenomena

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <cassert>
#include <numeric>

using namespace std;

using ll = long long;

struct BIT
{
    int n;
    vector<ll> tree;
    
    void update(int p, ll val)
    {
        for (;p < n; p |= p + 1) tree[p] += val;
    }
    
    BIT(vector<ll> a) : n((int)a.size())
    {
        tree.resize(n);
        for (int i = 0; i < n; ++i) update(i, a[i]);
    }
    
    ll get()
    {
        ll res = 0;
        for (int i = n - 1; i >= 0; i = (i & (i + 1)) - 1) res += tree[i];
        return res;
    }
    
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    ll s, t;
    cin >> n >> q >> s >> t;
    vector<ll> a(n);
    cin >> a.front();
    for (ll &i : a) cin >> i;
    adjacent_difference(a.begin(), a.end(), a.begin());
    vector<ll> help = a;
    for (ll &i : help)
    {
        if (i < 0) i *= -t;
        else i *= -s;
    }
    BIT st(help);
    while (q--)
    {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        //l - 1
        //r
        a[l - 1] += x;
        ll next = a[l - 1] * (a[l - 1] < 0 ? -t : -s);
        st.update(l - 1, next - help[l - 1]);
        help[l - 1] = next;
        if (r != n)
        {
            a[r] -= x;
            ll next = a[r] * (a[r] < 0 ? -t : -s);
            st.update(r, next - help[r]);
            help[r] = next;
        }
        cout << st.get() << '\n';
    }
    return 0;
}

/*
3 5 1 2
0 4 1 8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5
*/

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