| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287162 | MasterTaster | Watching (JOI13_watching) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"
#define MAXN 1000000000000000000
ll n, q, s, t, arr[200010], seg[800040], temp[200010], lazy[800040], segT[800040], lazyT[800040];
void relax(ll node, ll l, ll r)
{
ll val=lazy[node];
seg[node]+=lazy[node];
lazy[node]=0;
if (l!=r)
{
lazy[2*node]+=val;
lazy[2*node+1]+=val;
}
return;
}
void relaxT(ll node, ll l, ll r)
{
ll val=lazyT[node];
segT[node]+=lazyT[node];
lazyT[node]=0;
if (l!=r)
{
lazyT[2*node]+=val;
lazyT[2*node+1]+=val;
}
return;
}
void build(ll node, ll l, ll r)
{
if (l==r)
{
seg[node]=arr[l];
return;
}
ll mid=l+(r-l)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
return;
}
void buildT(ll node, ll l, ll r)
{
if (l==r)
{
//cout<<l<<" "<<temp[l]<<endl;
segT[node]=temp[l];
return;
}
ll mid=l+(r-l)/2;
buildT(2*node, l, mid);
buildT(2*node+1, mid+1, r);
return;
}
void update(ll node, ll l, ll r, ll levo, ll desno, ll val) ///l, r-gde sam u segmentnom; levo, desno-query
{
relax(node, l, r);
if (levo>r || desno<l) return;
if (levo<=l && desno>=r)
{
lazy[node]+=val;
return;
}
ll mid=l+(r-l)/2;
update(2*node, l, mid, levo, desno, val);
update(2*node+1, mid+1, r, levo, desno, val);
relax(2*node, l, mid);
relax(2*node+1, mid+1, r);
seg[node]=max(seg[2*node], seg[2*node+1]);
}
void updateT(ll node, ll l, ll r, ll levo, ll desno, ll val) ///l, r-gde sam u segmentnom; levo, desno-query
{
relaxT(node, l, r);
if (levo>r || desno<l) return;
if (levo<=l && desno>=r)
{
lazyT[node]+=val;
return;
}
ll mid=l+(r-l)/2;
updateT(2*node, l, mid, levo, desno, val);
updateT(2*node+1, mid+1, r, levo, desno, val);
relaxT(2*node, l, mid);
relaxT(2*node+1, mid+1, r);
segT[node]=max(segT[2*node], segT[2*node+1]);
}
ll query(ll node, ll l, ll r, ll levo, ll desno)
{
relax(node, l, r);
if (levo>r || desno<l) return (ll)-MAXN;
if (levo<=l && desno>=r) return seg[node];
ll mid=l+(r-l)/2;
return max(query(2*node, l, mid, levo, desno),
query(2*node+1, mid+1, r, levo, desno));
}
ll queryT(ll node, ll l, ll r, ll levo, ll desno)
{
relaxT(node, l, r);
if (levo>r || desno<l) return (ll)-MAXN;
if (levo<=l && desno>=r) { /*cout<<l<<" alo "<<segT[node]<<endl;*/ return segT[node]; }
ll mid=l+(r-l)/2;
return max(queryT(2*node, l, mid, levo, desno),
queryT(2*node+1, mid+1, r, levo, desno));
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>q>>s>>t;
for (int i=0; i<=n; i++) cin>>arr[i];
temp[0]=0;
for (int i=1; i<=n; i++)
{
if (arr[i]>arr[i-1]) temp[i]=temp[i-1]-s*(arr[i]-arr[i-1]);
else temp[i]=temp[i-1]+t*(arr[i-1]-arr[i]);
///cout<<temp[i]<<endl;
}
build(1, 0, n);
ll out=temp[n] ;
//buildT(1, 0, n);
//cout<<temp[n]<<" e "<<queryT(1, 0, n, n, n)<<endl;
///cout<<"ee"<<endl;
while (q--)
{
ll l, r, x;
cin>>l>>r>>x;
///A[i]>=A[i-1], T[i-1]-S*DELTA
///A[i]<A[i-1], T[i-1]+T*DELTA
ll delta=0;
if (l>0)
{
ll prvi, stariDrugi;
prvi=query(1, 0, n, l-1, l-1);
stariDrugi=query(1, 0, n, l, l);
ll noviDrugi=stariDrugi+x;
///cout<<stariPrvi<<" e "<<stariDrugi<<" e "<<noviDrugi<<endl;
if (x>=0)
{
if (stariDrugi<prvi)
{
delta-=t*(min(noviDrugi, prvi)-stariDrugi); ///OK
}
if (noviDrugi>=prvi)
{
delta-=s*(noviDrugi-max(stariDrugi, prvi));
}
}
else
{
if (stariDrugi>=prvi)
{
delta+=s*(stariDrugi-max(prvi, noviDrugi)); ///OK
}
if (noviDrugi<prvi)
{
delta+=t*(min(stariDrugi, prvi)-noviDrugi); ///OK
}
}
}
//if (delta!=0) updateT(1, 0, n, l, n, delta);
out+=delta;
///cout<<delta<<endl;
///cout<<"eej"<<endl;
delta=0;
if (r<n)
{
ll stariPrvi, drugi;
stariPrvi=query(1, 0, n, r, r);
drugi=query(1, 0, n, r+1, r+1);
ll noviPrvi=stariPrvi+x;
///cout<<stariPrvi<<" "<<stariDrugi<<" "<<noviPrvi<<endl;
if (x<0)
{
if (drugi<stariPrvi)
{
delta-=t*(stariPrvi-max(noviPrvi, drugi)); ///OK
}
if (drugi>=noviPrvi)
{
delta-=s*(min(drugi, stariPrvi)-noviPrvi); ///OK
}
}
else
{
///cout<<"ovde"<<endl;
if (drugi>=stariPrvi)
{
///cout<<"jee"<<endl;
delta+=s*(min(drugi, noviPrvi)-stariPrvi); ///OK
}
if (noviPrvi>drugi)
{
///cout<<"dvaa"<<endl;
delta+=t*(noviPrvi-max(stariPrvi, drugi)); ///OK
}
}
}
out+=delta
//if (delta!=0) updateT(1, 0, n, r+1, n, delta);
///cout<<delta<<endl;
//cout<<"eeej"<<endl;
update(1, 0, n, l, r, x);
cout<<out<<endl;
//cout<<"eeeej"<<endl;
//cout<<queryT(1, 0, n, n, n)<<endl;
}
}