이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"
struct segtree{
int sz = 1;
vector<int> a;
segtree(vector<int> &v){
while(sz < (int)v.size()) sz *= 2;
a.assign(2*sz, 0);
build(v, 0, 0, sz);
}
void build(vector<int> &v, int x, int lx, int rx){
if(rx-lx==1){
if(lx<(int)v.size()) a[x] = v[lx];
return;
}
int mx = (lx+rx)/2;
build(v, x+x+1, lx, mx);
build(v, x+x+2, mx, rx);
}
void update(int l, int r, int val, int x, int lx, int rx){
if(rx<=l or r<=lx) return;
if(l<=lx and rx<=r) return void(a[x] += val);
int mx = (lx+rx)/2;
update(l, r, val, x+x+1, lx, mx);
update(l, r, val, x+x+2, mx, rx);
}
void update(int l, int r, int val){ update(l, r+1, val, 0, 0, sz); }
int get(int i, int x, int lx, int rx){
if(rx-lx==1) return a[x];
int mx = (lx+rx)/2;
if(i<mx) return a[x] + get(i, x+x+1, lx, mx);
else return a[x] + get(i, x+x+2, mx, rx);
}
int get(int i){ return get(i, 0, 0, sz); }
};
int n, q, s, t;
int f(int x, int y){
return (x-y)*((x<y) ? s : t);
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q >> s >> t;
vector<int> a(n+1);
for(int &i : a) cin >> i;
int res = 0;
for(int i=0; i<n; ++i) res += f(a[i], a[i+1]);
segtree st(a);
while(q--){
int l, r, x; cin >> l >> r >> x;
res -= f(st.get(l-1), st.get(l));
if(r<n) res -= f(st.get(r), st.get(r+1));
st.update(l, r, x);
res += f(st.get(l-1), st.get(l));
if(r<n) res += f(st.get(r), st.get(r+1));
cout << res nl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |