Submission #206077

#	Time	Username	Problem	Language	Result	Execution time	Memory
206077		stefdasca	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	218 ms	12408 KiB

foehn_phenomena

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

typedef long long ll;

int n, q, s, t, v[200002];
ll ts;
ll aib[200002];
void add(int nod, int val)
{
    for(; nod <= n; nod += (nod & (-nod)))
        aib[nod] += val;
}
ll compute(int nod)
{
    ll ans = 0;
    for(; nod; nod -= (nod & (-nod)))
        ans += aib[nod];
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q >> s >> t;
    for(int i = 0; i <= n; ++i)
        cin >> v[i];
    for(int i = 0; i < n; ++i)
        if(v[i] < v[i+1])
            ts = ts - 1LL * s * (v[i+1] - v[i]);
        else
            ts = ts + 1LL * t * (v[i] - v[i+1]);
    for(; q; --q)
    {
        int st, dr, val;
        cin >> st >> dr >> val;
        if(v[st - 1] + compute(st - 1) < v[st] + compute(st))
            ts = ts + 1LL * s * (v[st] + compute(st) - v[st - 1] - compute(st - 1));
        else
            ts = ts - 1LL * t * (v[st - 1] + compute(st - 1) - v[st] - compute(st));
        if(dr != n)
        {
            if(v[dr] + compute(dr) < v[dr + 1] + compute(dr + 1))
                ts = ts + 1LL * s * (v[dr + 1] + compute(dr + 1) - v[dr] - compute(dr));
            else
                ts = ts - 1LL * t * (v[dr] + compute(dr) - v[dr + 1] - compute(dr + 1));
        }
        add(st, val);
        add(dr + 1, -val);
        if(v[st - 1] + compute(st - 1) < v[st] + compute(st))
            ts = ts - 1LL * s * (v[st] + compute(st) - v[st - 1] - compute(st - 1));
        else
            ts = ts + 1LL * t * (v[st - 1] + compute(st - 1) - v[st] - compute(st));
        if(dr != n)
        {
            if(v[dr] + compute(dr) < v[dr + 1] + compute(dr + 1))
                ts = ts - 1LL * s * (v[dr + 1] + compute(dr + 1) - v[dr] - compute(dr));
            else
                ts = ts + 1LL * t * (v[dr] + compute(dr) - v[dr + 1] - compute(dr + 1));
        }
        cout << ts << '\n';
    }
    return 0;
}

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