제출 #991167

#제출 시각아이디문제언어결과실행 시간메모리
991167aaaaaarrozFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
350 ms16980 KiB
#include<bits/stdc++.h> const char nl = '\n'; using namespace std; using ll = long long; ll s, t; struct Segtree { struct node { ll le, ri, wd; }; vector<ll> tree; vector<ll> sh; vector<ll> a; ll sz = 1; ll nope = 0; void init(ll n) { while (sz < n) { sz *= 2; } tree.assign(2*sz+1, 0); sh.assign(2*sz+1, 0); a.assign(n+10, 0); } void create(ll n) { for (ll i = 0, lf = sz-1; i <= n; i ++, lf ++) { tree[lf] = a[i]; } } void build(ll x, ll lx, ll rx) { if (rx - lx == 1) { return ; } ll mid = (lx + rx) / 2; build(2*x+1, lx, mid); build(2*x+2, mid, rx); tree[x] = tree[2*x+1] + tree[2*x+2]; } void build() { build(0, 0, sz); } void push(ll x, ll lx, ll rx) { if (sh[x] == nope) return ; if (rx - lx == 1) return ; sh[2*x+1] += sh[x]; tree[2*x+1] += sh[x]; sh[2*x+2] += sh[x]; tree[2*x+2] += sh[x]; sh[x] = nope; } void update(ll l, ll r, ll v, ll x, ll lx, ll rx) { push(x, lx, rx); if (lx >= r || rx <= l) { return ; } if (l <= lx && rx <= r) { sh[x] += v; push(x, lx, rx); tree[x] += v; return ; } ll mid = (lx + rx) / 2; update(l, r, v, 2*x+1, lx, mid); update(l, r, v, 2*x+2, mid, rx); tree[x] = tree[2*x+1] + tree[2*x+2]; } void update(ll l, ll r, ll v) { update(l, r, v, 0, 0, sz); } ll get(ll i, ll x, ll lx, ll rx) { push(x, lx, rx); if (rx - lx == 1) { return tree[x]; } ll mid = (lx + rx) / 2; if (i < mid) { return get(i, 2*x+1, lx, mid); } else { return get(i, 2*x+2, mid, rx); } } ll get(ll i) { return get(i, 0, 0, sz); } void debug() { for (ll i = 0; i < 2*sz-1; i ++) { cout << i << ": " << tree[i] << nl; } } }; ll wind(ll x, ll y) { return (x < y ? s * (x - y) : t * (x - y)); } void solve() { ll n, q; cin >> n >> q >> s >> t; Segtree sg; n ++; sg.init(n); for (ll i = 0; i < n; i ++) { cin >> sg.a[i]; } sg.create(n); sg.build(); ll res = 0; for (ll i = 0; i < n-1; i ++) { res += wind(sg.a[i], sg.a[i+1]); } for (ll i = 0; i < q; i ++) { ll l, r, v; cin >> l >> r >> v; r ++; res -= wind(sg.get(l-1), sg.get(l)); if (r != n) { res -= wind(sg.get(r-1), sg.get(r)); } sg.update(l, r, v); res += wind(sg.get(l-1), sg.get(l)); if (r != n) { res += wind(sg.get(r-1), sg.get(r)); } cout << res << nl; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll tst = 1; while (tst --) { solve(); cout << nl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...