Submission #1293997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293997		hynmj	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	538 ms	13712 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1ll << 18;
int p[N << 3];
int ng[N << 3];
void addp(int i, int val, int cur = 1, int l = 1, int r = N)
{
    if (i < l || i > r)
        return;
    if (l == r)
    {
        p[cur] = val;
        return;
    }
    int lc = cur << 1, rc = lc | 1, mid = (l + r) >> 1;
    addp(i, val, lc, l, mid);
    addp(i, val, rc, mid + 1, r);
    p[cur] = p[lc] + p[rc];
}

void addn(int i, int val, int cur = 1, int l = 1, int r = N)
{
    if (i < l || i > r)
        return;
    if (l == r)
    {
        ng[cur] = val;
        return;
    }
    int lc = cur << 1, rc = lc | 1, mid = (l + r) >> 1;
    addn(i, val, lc, l, mid);
    addn(i, val, rc, mid + 1, r);
    ng[cur] = ng[lc] + ng[rc];
}

int getPos(int L, int R, int cur = 1, int l = 1, int r = N)
{
    if (R < l || L > r)
        return 0;
    if (L <= l && r <= R)
        return p[cur];
    int lc = cur << 1, rc = lc | 1, mid = (l + r) >> 1;
    return getPos(L, R, lc, l, mid) + getPos(L, R, rc, mid + 1, r);
}

int getNeg(int L, int R, int cur = 1, int l = 1, int r = N)
{
    if (R < l || L > r)
        return 0;
    if (L <= l && r <= R)
        return ng[cur];
    int lc = cur << 1, rc = lc | 1, mid = (l + r) >> 1;
    return getNeg(L, R, lc, l, mid) + getNeg(L, R, rc, mid + 1, r);
}

int d[N];
int a[N];
void solve()
{
    int n, q, s, t;
    cin >> n >> q >> s >> t;
    cin >> a[0];
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        d[i] = a[i] - a[i - 1];
        if (d[i] >= 0)
            addp(i, d[i]);
        else
            addn(i, d[i]);
    }
    for (int i = 0; i < q; i++)
    {
        int l, r, x;
        cin >> l >> r >> x;
        d[l] += x;
        if (d[l] >= 0)
        {
            addn(l, 0);
            addp(l, d[l]);
        }
        else
        {
            addp(l, 0);
            addn(l, d[l]);
        }
        if (r != n)
        {
            int idx = r + 1;
            d[idx] -= x;
            if (d[idx] >= 0)
            {
                addn(idx, 0);
                addp(idx, d[idx]);
            }
            else
            {
                addp(idx, 0);
                addn(idx, d[idx]);
            }
        }
        int psum = getPos(1, n);
        int nsum = getNeg(1, n);
        cout << -(psum * s) - (nsum * t) << endl;
        }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << ':' << ' ';
        solve();
        cout << endl;
    }
    return 0;
}

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