이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=200007;
ll n,m,k;
ll t[4*N];
ll lazy[8*N];
ll a[N];
void push(int v, int tl, int tr){
if(lazy[v]!=0){
int len=tr-tl+1;
t[v]+=lazy[v]*len;
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v]=0;
}
}
void build(int v, int tl, int tr){
if(tl==tr){
t[v]=a[tl];
}
else{
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=t[2*v]+t[2*v+1];
}
}
void add(int v, int tl, int tr, int l, int r, ll vl){
push(v,tl,tr);
if(l>r)return;
if(l==tl&&r==tr){
lazy[v]+=vl;
push(v,tl,tr);
}
else{
int tm=(tl+tr)/2;
add(2*v,tl,tm,l,min(r,tm),vl);
push(v,tl,tr);
add(2*v+1,tm+1,tr,max(tm+1,l),r,vl);
push(v,tl,tr);
t[v]=t[2*v]+t[2*v+1];
}
}
int getsum(int v, int tl, int tr, int l, int r){
push(v,tl,tr);
if(l>r)return 0;
if(tl==l&&tr==r){
return t[v];
}
else{
int tm=(tl+tr)/2;
push(v,tl,tr);
return getsum(2*v,tl,tm,l,min(r,tm))+
getsum(2*v+1,tm+1,tr,max(tm+1,l),r);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("Ainput.txt","r",stdin);
// freopen("Aoutput.txt","w",stdout);
ll s,t;
cin>>n>>m>>s>>t;
n++;
for(int i=0;i<n;i++){
cin>>a[i];
}
build(1,0,n-1);
ll ans=0;
for(int i=0;i<n-1;i++){
if(a[i]<a[i+1]){
ans-=s*(a[i+1]-a[i]);
}
else{
ans+=t*(a[i]-a[i+1]);
}
}
for(int i=0;i<m;i++){
int l,r;
ll w;
cin>>l>>r>>w;
a[l-1]=getsum(1,0,n-1,l-1,l-1);
a[l]=getsum(1,0,n-1,l,l);
// cout<<a[l-1]<<" "<<a[l]<<endl;
// cout<<"OK"<<endl;
if(r!=n-1){
a[r]=getsum(1,0,n-1,r,r);
a[r+1]=getsum(1,0,n-1,r+1,r+1);
// cout<<a[r]<<" "<<a[r+1]<<endl;
}
if(a[l-1]<a[l]){
ans+=s*(a[l]-a[l-1]);
}
else{
ans-=t*(a[l-1]-a[l]);
}
if(r!=n-1){
if(a[r]<a[r+1]){
ans+=s*(a[r+1]-a[r]);
}
else{
ans-=t*(a[r]-a[r+1]);
}
}
add(1,0,n-1,l,r,w);
a[l-1]=getsum(1,0,n-1,l-1,l-1);
a[l]=getsum(1,0,n-1,l,l);
// cout<<a[l-1]<<" "<<a[l]<<endl;
// cout<<"OK"<<endl;
if(r!=n-1){
a[r]=getsum(1,0,n-1,r,r);
a[r+1]=getsum(1,0,n-1,r+1,r+1);
// cout<<a[r]<<" "<<a[r+1]<<endl;
}
if(a[l-1]<a[l]){
ans-=s*(a[l]-a[l-1]);
}
else{
ans+=t*(a[l-1]-a[l]);
}
if(r!=n-1){
if(a[r]<a[r+1]){
ans-=s*(a[r+1]-a[r]);
}
else{
ans+=t*(a[r]-a[r+1]);
}
}
cout<<ans<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |