Submission #1051550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051550		SamAnd	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	120 ms	13140 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;

int n, q;
ll S, T;
ll a[N];

ll t[N];
void ubd(int x, ll y)
{
    while (x <= n)
    {
        t[x] += y;
        x += (x & (-x));
    }
}

ll qry(int x)
{
    ll ans = 0;
    while (x)
    {
        ans += t[x];
        x -= (x & (-x));
    }
    return ans;
}

void solv()
{
    cin >> n >> q >> S >> T;
    for (int i = 0; i <= n; ++i)
        cin >> a[i];

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] < a[i + 1])
            ans += S * (a[i] - a[i + 1]);
        else
            ans += T * (a[i] - a[i + 1]);
    }

    for (int i = 1; i <= n; ++i)
    {
        ubd(i, a[i]);
        ubd(i + 1, -a[i]);
    }

    while (q--)
    {
        int l, r;
        ll y;
        cin >> l >> r >> y;

        if (qry(l - 1) < qry(l))
            ans -= S * (qry(l - 1) - qry(l));
        else
            ans -= T * (qry(l - 1) - qry(l));
        if (r < n)
        {
            if (qry(r) < qry(r + 1))
                ans -= S * (qry(r) - qry(r + 1));
            else
                ans -= T * (qry(r) - qry(r + 1));
        }

        ubd(l, y);
        ubd(r + 1, -y);

        if (qry(l - 1) < qry(l))
            ans += S * (qry(l - 1) - qry(l));
        else
            ans += T * (qry(l - 1) - qry(l));
        if (r < n)
        {
            if (qry(r) < qry(r + 1))
                ans += S * (qry(r) - qry(r + 1));
            else
                ans += T * (qry(r) - qry(r + 1));
        }

        cout << ans << "\n";
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

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