Submission #529696

#	Time	Username	Problem	Language	Result	Execution time	Memory
529696		leu_naut	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	379 ms	15576 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5;
const int MOD = 1e9 + 7;
const ll oo = 1e18;

int n,q,s,t;
ll ST[4 * N + 5], lazy[N + 5], a[N + 5];

void down(int id)
{
    int tmp = lazy[id];
    lazy[id * 2] += tmp;
    lazy[id * 2 + 1] += tmp;
    ST[id * 2] += tmp;
    ST[id * 2 + 1] += tmp;
    lazy[id] = 0;
}

void upd(int id, int l, int r, int u, int v, int val)
{
    if (r < u || v < l) return ;
    if (u <= l && r <= v) {
        ST[id] += val;
        lazy[id] += val;
        return ;
    }
    int mid = (l + r) >> 1;
    down(id);
    upd(id * 2,l,mid,u,v,val);
    upd(id * 2 + 1,mid + 1,r,u,v,val);
    ST[id] = max(ST[id * 2], ST[id * 2 + 1]);
}

int get(int id, int l, int r, int u, int v)
{
    if (r < u || v < l) return 0;
    if (u <= l && r <= v) return ST[id];
    int mid = (l + r) >> 1;
    down(id);
    return get(id * 2,l,mid,u,v) + get(id * 2 + 1,mid + 1,r,u,v);
}

int main()
{
    ios_base::sync_with_stdio(0);  cin.tie(0);
    cin >> n >> q >> s >> t;
    for (int i = 0; i <= n; ++i) cin >> a[i], upd(1,1,n,i,i,a[i]);
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        ll tmp = llabs(a[i] - a[i + 1]);
        if (a[i] < a[i + 1]) sum += -tmp * s;
        else sum += tmp * t;
    }
    for (int i = 1; i <= q; ++i) {
        int l,r,x;
        cin >> l >> r >> x;
        ll tmp = llabs(a[l] - a[l - 1]);
        if (a[l] > a[l - 1]) sum += tmp * s;
        else sum += -tmp * t;
        if (r != n) {
            tmp = llabs(a[r] - a[r + 1]);
            if (a[r] < a[r + 1]) sum += tmp * s;
            else sum += -tmp * t;
        }
        upd(1,1,n,l,r,x);
        a[l] = get(1,1,n,l,l);
        a[r] = get(1,1,n,r,r);
        //cout << a[l] << ' ' << a[r] << '\n';
        tmp = llabs(a[l] - a[l - 1]);
        if (a[l] > a[l - 1]) sum += -tmp * s;
        else sum += tmp * t;
        if (r != n) {
            tmp = llabs(a[r] - a[r + 1]);
            if (a[r] < a[r + 1]) sum += -tmp * s;
            else sum += tmp * t;
        }
        cout << sum << '\n';
    }
}

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