제출 #1345158

#제출 시각아이디문제언어결과실행 시간메모리
1345158thaibaotran555Foehn Phenomena (JOI17_foehn_phenomena)C++20
100 / 100
233 ms16112 KiB
///TRAN THAI BAO :3

#include <iostream>
#include <cstdio>

using namespace std;

#define maxN 200007

int n, q;
long long s, t;
long long a[maxN];
long long curAns = 0;

struct SEG
{
    long long st[maxN*4];
    long long lazy[maxN*4] = {0};
    void build(int id, int l, int r)
    {
        if(l == r)
        {
            st[id] = a[l];
            return;
        }
        int mid = (l+r)/2;
        build(id*2, l, mid);
        build(id*2+1, mid+1, r);
        st[id] = st[id*2] + st[id*2+1];
    }
    void fix(int id, int l, int r)
    {
        if(lazy[id] == 0)
            return;
        st[id] += lazy[id]*(r-l+1);
        if(l != r)
        {
            lazy[id*2] += lazy[id];
            lazy[id*2+1] += lazy[id];
        }
        lazy[id] = 0;
    }
    void update(int id, int l, int r, int u, int v, long long val)
    {
        fix(id, l, r);
        if(l > v || u > r)
            return;
        if(u <= l && r <= v)
        {
            lazy[id] += val;
            fix(id, l, r);
            return;
        }
        int mid = (l+r)/2;
        update(id*2, l, mid, u, v, val);
        update(id*2+1, mid+1, r, u, v, val);
        st[id] = st[id*2] + st[id*2+1];
    }
    long long query(int id, int l, int r, int u, int v)
    {
        fix(id, l, r);
        if(l > v || u > r)
            return 0;
        if(u <= l && r <= v)
            return st[id];
        int mid = (l+r)/2;
        return query(id*2, l, mid, u, v) + query(id*2+1, mid+1, r, u, v);
    }
};

SEG seg;

long long getVal(long long pre, long long nxt)
{
    long long ans;
    if(pre < nxt)
        ans = -s*(nxt - pre);
    else ans = t*(pre - nxt);
    return ans;
}

void readData()
{
    cin >> n >> q >> s >> t;
    n++;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 2; i <= n; i++)
        curAns += getVal(a[i-1], a[i]);
}

void solve()
{
    seg.build(1, 1, n);
    int l, r;
    long long addVal;
    while(q--)
    {
        cin >> l >> r >> addVal;
        l++;
        r++;
        if(l > 1)
        {
            long long pre = seg.query(1, 1, n, l-1, l-1);
            long long cur = seg.query(1, 1, n, l, l);
            curAns -= getVal(pre, cur);
            curAns += getVal(pre, cur+addVal);
        }
        if(r < n)
        {
            long long pre = seg.query(1, 1, n, r, r);
            long long cur = seg.query(1, 1, n, r+1, r+1);
            curAns -= getVal(pre, cur);
            curAns += getVal(pre+addVal, cur);
        }
        seg.update(1, 1, n, l, r, addVal);
        cout << curAns << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    readData();
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...