이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
const int mod= 1e17 +7;
const int N=2e5 + 5 ;
const int inf = 1e17 + 7;
int binpow (int a, int n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return binpow (a, n-1) * a;
else {
int b = binpow (a, n/2);
return b * b;
}
}
int n,m,k,q;
int t[N * 4], bn[N * 4], h[N * 4], hi[N * 4];
void push(int tl, int tr, int v){
if(tl != tr){
bn[v * 2] += bn[v];
bn[v * 2 + 1] += bn[v];
}
t[v] += bn[v];
bn[v] = 0;
}
void update(int tl,int tr,int v,int l,int r,int val){
push(tl,tr,v);
if(r<tl||tr<l)return;
if(l<=tl&&tr<=r){
bn[v] += val;
push(tl,tr,v);
//~ cout<<t[v]<<"\n";
return;
}
int tm = (tl + tr) / 2;
update(tl,tm,v * 2,l,r,val);
update(tm+1,tr,v * 2 + 1,l,r,val);
}
int get(int tl,int tr, int v,int pos){
push(tl,tr,v);
if(tl == tr){
//~ cout<<v<<"\n";
return t[v];
}
int tm = (tl + tr)/2;
if(pos <= tm)return get(tl,tm,v * 2,pos);
else return get(tm+1,tr,v * 2 + 1,pos);
}
//-----------------------------------------------------------------------------------------------------------------------------------------------------
void push1(int tl, int tr, int v){
if(tl != tr){
hi[v * 2] += hi[v];
hi[v * 2 + 1] += hi[v];
}
h[v] += hi[v];
hi[v] = 0;
}
void update1(int tl,int tr,int v,int l,int r,int val){
push1(tl,tr,v);
if(r<tl||tr<l)return;
if(l<=tl&&tr<=r){
hi[v] += val;
push1(tl,tr,v);
return;
}
int tm = (tl + tr) / 2;
update1(tl,tm,v * 2,l,r,val);
update1(tm+1,tr,v * 2 + 1,l,r,val);
}
int get1(int tl,int tr, int v,int pos){
push1(tl,tr,v);
if(tl == tr){
return h[v];
}
int tm = (tl + tr)/2;
if(pos <= tm)return get1(tl,tm,v * 2,pos);
else return get1(tm+1,tr,v * 2 + 1,pos);
}
void solve(){
cin >> n >> q >> m >> k;
vector<int>v(n + 1);
for(int i = 0;i<=n;i++){
cin>>v[i];
}
int last = 0;
for(int i = 1;i<=n;i++){
if(v[i - 1] >= v[i]){
last += (v[i - 1] - v[i]) * k;
}
else{
last -= (v[i] - v[i - 1]) * m;
}
update(1,n,1,i,i,last);
//~ cout<<get(1,n,1,i)<<"\n";
}
for(int i = 1;i<=n;i++){
update1(1,n,1,i,i,v[i]);
}
//~ cout<<get(1,n,1,n)<<"\n";
while(q--){
int l,r,val;
cin>>l>>r>>val;
int h1 = 0; if(l > 1)h1 = get1(1,n,1,l - 1);
int h2 = get1(1,n,1,l);
int dif = 0;
if(h1 > h2)dif += (h1 - h2) * k;
else dif -= (h2 - h1) * m;
int dif1 = 0; h2 += val;
if(h1 > h2)dif1 += (h1 - h2) * k;
else dif1 -= (h2 - h1) * m;
int sum1 = dif1 - dif;
//~ cout<<h1<<" "<<h2<<" "<<dif<<" "<<dif1<<"\n";
if(r < n){
h1 = get1(1,n,1,r);
h2 = get1(1,n,1,r + 1);
dif = 0;
if(h1 > h2)dif += (h1 - h2) * k;
else dif -= (h2 - h1) * m;
dif1 = 0; h1 += val;
if(h1 > h2)dif1 += (h1 - h2) * k;
else dif1 -= (h2 - h1) * m;
update(1,n,1,r + 1,n,dif1 - dif);
}
update(1,n,1,l,n,sum1);
update1(1,n,1,l,r,val);
cout<<get(1,n,1,n)<<"\n";
}
}
signed main()
{
// freopen("seq.in", "r", stdin);
// freopen("seq.out", "w", stdout);
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int tt=1;//cin>>tt>>n;
while(tt--)solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |