제출 #529729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529729		leu_naut	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	645 ms	19848 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;

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

void down(int id)
{
    ll 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, ll 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]);
}

ll 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);
}

ll calc(int l, int r, int tp)
{
    if (l < 0 || r > n) return 0;
    //cout << l << ' ' << r << '\n';
    ll ans = 0, tmp = llabs(a[r] - a[l]);
    if (a[l] < a[r]) ans = tp * -tmp * s;
    else ans = tp * tmp * t;
    return ans;
}

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; //*/
        sum += calc(i,i + 1,1);
    }
    //cout << sum << '\n';
    for (int i = 1; i <= q; ++i) {
        int l,r,x;
        cin >> l >> r >> x;
        a[l] = get(1,1,n,l,l);
        a[r] = get(1,1,n,r,r);
        a[l - 1] = get(1,1,n,l - 1,l - 1);
        a[r + 1] = get(1,1,n,r + 1, r + 1);
        //cout << l << ' ' << r << ' ' << a[l] << ' ' << a[r] << '\n';
        sum += calc(l - 1,l,-1);
        sum += calc(r, r + 1,-1);

        //cout << sum << '\n';

        upd(1,1,n,l,r,x);
        a[l] = get(1,1,n,l,l);
        a[r] = get(1,1,n,r,r);
        a[l - 1] = get(1,1,n,l - 1,l - 1);
        a[r + 1] = get(1,1,n,r + 1, r + 1);
        //cout << a[l] << ' ' << a[r] << '\n';

        sum += calc(l - 1,l,1);
        sum += calc(r, r + 1,1);
        //cout << "End" << ' ' << i << '\n';
        cout << sum << '\n';
    }
}

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