이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int long long
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=(ll)a;i<=(ll)b;++i)
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
const int mxN = 2e5+7, base = 1<<18;
int a[mxN], tree[base<<1];
void init(int n){
rep(i,0,n) tree[i+base] = a[i];
}
void add(int l,int r,int x){
l += base-1;
r += base+1;
while(r-l > 1){
if(!(l&1)) tree[l+1] += x;
if(r&1) tree[r-1] += x;
l /= 2; r /= 2;
}
}
int que(int v){
v += base;
int res = tree[v];
while(v){
v /= 2;
res += tree[v];
}
return res;
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q,s,t; cin >> n >> q >> s >> t;
rep(i,0,n) cin >> a[i];
init(n);
int rosnie = 0, spada = 0;
rep(i,1,n) if(a[i] > a[i-1]) rosnie += a[i]-a[i-1];
rep(i,1,n) if(a[i] < a[i-1]) spada += a[i-1]-a[i];
while(q--){
int l,r,x; cin >> l >> r >> x;
if(que(l) > que(l-1)) rosnie -= que(l)-que(l-1);
if(r < n) if(que(r+1) > que(r)) rosnie -= que(r+1)-que(r);
if(que(l) < que(l-1)) spada += que(l)-que(l-1);
if(r < n) if(que(r+1) < que(r)) spada += que(r+1)-que(r);
add(l,r,x);
if(que(l) > que(l-1)) rosnie += que(l)-que(l-1);
if(r < n) if(que(r+1) > que(r)) rosnie += que(r+1)-que(r);
if(que(l) < que(l-1)) spada -= que(l)-que(l-1);
if(r < n) if(que(r+1) < que(r)) spada -= que(r+1)-que(r);
cout << -rosnie*s + spada*t << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |