Submission #1310074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310074		zxzuam	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	233 ms	13908 KiB

foehn_phenomena

#include<bits/stdc++.h>
#define int long long
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
/*template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}*/
constexpr int maxn = 2e5 + 9, mod = 1e9 + 7, P = 257, MOD = 1e9 + 9;
int t[maxn * 4], f[maxn * 4], a[maxn];
void build(int v, int tl, int tr) {
    if(tl == tr) {
        t[v] = a[tl];
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v] = t[v * 2] + t[v * 2 + 1];
}
void push(int v, int tl, int tr) {
    if(f[v]) {
        t[v] += f[v] * (tr - tl + 1);
        if(tr > tl) {
            f[v * 2] += f[v];
            f[v * 2 + 1] += f[v];
        }
        f[v] = 0;
    }
}
void upd(int v, int tl, int tr, int l, int r, int x) {
    if(l > tr || tl > r || l > r) return;
    push(v, tl, tr);
    if(l <= tl && tr <= r) {
        f[v] += x;
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) >> 1;
    upd(v * 2, tl, tm, l, r, x);
    upd(v * 2 + 1, tm + 1, tr, l, r, x);
    t[v] = t[v * 2] + t[v * 2 + 1];
}
int get(int v, int tl, int tr, int i) {
    if(i == 0) return 0;
    if(i < tl || tr < i) return 0;
    push(v, tl, tr);
    if(tl == tr) return t[v];
    int tm = (tl + tr) >> 1;
    if(i <= tm) return get(v * 2, tl, tm, i);
    return get(v * 2 + 1, tm + 1, tr, i);
}
int n, q, s, T;
inline int ff(int x, int y) {
    if(x >= y) {
        return (x - y) * T;
    }
    return -((y - x) * s);
}
void solve(){
    cin >> n >> q >> s >> T;
    cin >> a[0];
    int res = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        if(a[i] <= a[i - 1]) {
            res += (a[i - 1] - a[i]) * T;
        }
        else{
            res -= (a[i] - a[i - 1]) * s;
        }
    }
    build(1, 1, n);
    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        int xl = get(1, 1, n, l - 1), yl = get(1, 1, n, l);
        int xr, yr;
        res -= ff(xl, yl);
        if(r != n) {
            xr = get(1, 1, n, r), yr = get(1, 1, n, r + 1);
            res -= ff(xr, yr);
        }
        upd(1, 1, n, l, r, x);
        yl += x;
        res += ff(xl, yl);
        if(r != n) {
            xr += x;
            res += ff(xr, yr);
        }
        cout << res << '\n';
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
        solve();
    }
}

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