Submission #1310162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310162		thecrazycandy	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	0 / 100	264 ms	5280 KiB

foehn_phenomena

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
#define ll int
#define sped_up ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define S second
#define F first
const ll INF = (ll)1e9 + 1, INFL = (ll)1e18 + 1;
const ll mod = (ll)1e9 + 7, MAXN = (ll)2e5 + 1;
ll a[MAXN], t[MAXN * 4];
void build (ll v, ll tl, ll tr) {
    if (tl == tr) t[v] = a[tl];
    if (tl == tr) return;
    ll tm = (tl + tr) / 2;
    build (v * 2, tl, tm);
    build (v * 2 + 1, tm + 1, tr);
    t[v] = 0;
}
ll get (ll v, ll tl, ll tr, ll i) {
    if (tl == tr) return t[v];
    ll tm = (tl + tr) / 2;
    if (i <= tm) return t[v] + get(v * 2, tl, tm, i);
    else return t[v] + get(v * 2 + 1, tm + 1, tr, i);
}
void upd (ll v, ll tl, ll tr, ll l, ll r, ll x) {
    if (l <= tl && tr <= r) t[v] += x;
    if (l <= tl && tr <= r) return;
    if (l > tr || tl > r) return;
    ll tm = (tl + tr) / 2;
    upd (v * 2, tl, tm, l, r, x);
    upd (v * 2 + 1, tm + 1, tr, l, r, x);
}
int main() {
    sped_up;
    ll n, q, s, t;
    cin >> n >> q >> s >> t;
    ll cnt = 0;
    for (int i = 0; i <= n; i++) {
        cin >> a[i];
        if (i != 0) {
            if (a[i] > a[i - 1]) cnt -= s * (a[i] - a[i - 1]);
            else cnt -= t * (a[i] - a[i - 1]);
        }
    }
    build (1, 0, n);
    while (q--) {
        ll L, R, x;
        cin >> L >> R >> x;
        ll r1 = 0;
        ll l = get(1, 0, n, L);
        ll r = get(1, 0, n, R);
        ll l1 = get(1, 0, n, L - 1);
        if (R != n) r1 = get(1, 0, n, R + 1);
        else r1 = r;
        if (l > l1) cnt += s * (l - l1);
        else cnt += t * (l - l1);
        if (r1 > r) cnt += s * (r1 - r);
        else cnt += t * (r1 - r);
        upd (1, 0, n, L, R, x);
        r1 = 0;
        l = get(1, 0, n, L);
        r = get(1, 0, n, R);
        l1 = get(1, 0, n, L - 1);
        if (R != n) r1 = get(1, 0, n, R + 1);
        else r1 = r;
        if (l > l1) cnt -= s * (l - l1);
        else cnt -= t * (l - l1);
        if (r1 > r) cnt -= s * (r1 - r);
        else cnt -= t * (r1 - r);
        cout << cnt << '\n';
    }
}

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