이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=2*1e5+7;
vector<ll> bit1(MAX,0);
vector<ll> bit2(MAX,0);
vector<ll> incr(MAX,0);
vector<ll> decr(MAX,0);
ll n;
void upd1(int pos, ll val) {
while (pos<=n) {
bit1[pos]+=val;
pos+=pos&-pos;
}
}
void upd2(int pos, ll val) {
while (pos<=n) {
bit2[pos]+=val;
pos+=pos&-pos;
}
}
ll query1(int pos) {
ll ans=0;
while (pos>0) {
ans+=bit1[pos];
pos-=pos&-pos;
}
return ans;
}
ll query2(int pos) {
ll ans=0;
while (pos>0) {
ans+=bit2[pos];
pos-=pos&-pos;
}
return ans;
}
int main() {
ll q,s,t; cin>>n>>q>>s>>t;
vector<ll> a(n+1);
for (int i=0; i<=n; i++) cin>>a[i];
for (int i=1; i<=n; i++) {
if (a[i]>a[i-1]) {
incr[i]=a[i]-a[i-1];
upd1(i,incr[i]);
}
else {
decr[i]=a[i-1]-a[i];
upd2(i,decr[i]);
}
}
while (q--) {
ll l,r,x; cin>>l>>r>>x;
if (incr[l]!=0) {
if (incr[l]+x>=0) {
upd1(l,x);
incr[l]+=x;
}
else {
upd2(l,-x-incr[l]);
decr[l]+=-x-incr[l];
upd1(l,-incr[l]);
incr[l]+=-incr[l];
}
} else {
x=-x;
if (decr[l]+x>=0) {
upd2(l,x);
decr[l]+=x;
}
else {
upd1(l,-x-decr[l]);
incr[l]+=-x-decr[l];
upd2(l,-decr[l]);
decr[l]+=-decr[l];
}
x=-x;
}
if (r<n) {
x=-x;
l=r+1;
if (incr[l]!=0) {
if (incr[l]+x>=0) {
upd1(l,x);
incr[l]+=x;
}
else {
upd2(l,-x-incr[l]);
decr[l]+=-x-incr[l];
upd1(l,-incr[l]);
incr[l]+=-incr[l];
}
} else {
x=-x;
if (decr[l]+x>=0) {
upd2(l,x);
decr[l]+=x;
}
else {
upd1(l,-x-decr[l]);
incr[l]+=-x-decr[l];
upd2(l,-decr[l]);
decr[l]+=-decr[l];
}
x=-x;
}
}
cout<<t*query2(n)-s*query1(n)<<"\n";
}
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... |