이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pld pair<long double, int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define ff first
#define ss second
#define SZ(x) ((int)(x).size())
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e5+100;
int N, Q;
ll S, T, a[MAXN];
void read(){
cin >> N >> Q >> S >> T;
for(int i = 0; i <= N; i++){
cin >> a[i];
}
}
ll b[MAXN];
void add(int i, int k){
for(; i < MAXN; i += (i & -i))
b[i] += k;
}
ll get(int i){
ll s = 0;
for(; i > 0; i -= (i & -i))
s += b[i];
return s;
}
pll compare(int i){
pll diff = {0, 0};
ll ob1 = get(i), ob2 = get(i-1);
if(i - 1 >= 0 && ob1 > ob2){
diff.ss += ob1 - ob2;
} else if(i - 1 >= 0 && ob2 > ob1){
diff.ff += ob2 - ob1;
}
return diff;
}
ll ans;
pll cur;
void preprocess(){
for(int i = 1; i <= N; i++){
add(i, a[i]);
add(i+1, -a[i]);
}
for(int i = 1; i <= N; i++){
pll diff = compare(i);
cur.ff += diff.ff, cur.ss += diff.ss;
}
ans = cur.ff * T - cur.ss * S;
}
void update(int l, int r, int x){
pll diff;
diff = compare(l);
cur.ff -= diff.ff, cur.ss -= diff.ss;
if(r+1 <= N){
diff = compare(r+1);
cur.ff -= diff.ff, cur.ss -= diff.ss;
}
add(l, x);
add(r+1, -x);
diff = compare(l);
cur.ff += diff.ff, cur.ss += diff.ss;
if(r+1 <= N){
diff = compare(r+1);
cur.ff += diff.ff, cur.ss += diff.ss;
}
ans = cur.ff * T - cur.ss * S;
}
void solve(){
read();
preprocess();
while(Q--){
int l, r, x;
cin >> l >> r >> x;
update(l, r, x);
cout << ans << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |