제출 #931118

#제출 시각아이디문제언어결과실행 시간메모리
931118De3b0oFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
409 ms22508 KiB
#include<bits/stdc++.h> #define ll long long #define F first #define S second #define in insert #define er erase #define pb push_back #define ppb pop_back() #define ph push #define pp pop() #define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define cans cout << ans << "\n"; #define yes cout << "YES" << "\n"; #define no cout << "NO" << "\n"; #define pll pair<ll,ll> #define lin cout << "\n"; #define sqr 340 #define mod 1000000007 #define mid (l+r)/2 using namespace std; ll seg[800009]; ll lazy[800009]; ll a[200009]; void sb(ll n , ll l , ll r) { if(l==r) { seg[n]=a[l]; return; } sb(2*n,l,mid); sb(2*n+1,mid+1,r); seg[n]=seg[2*n]+seg[2*n+1]; } ll sg(ll n , ll l , ll r , ll i) { if(l>i||r<i) return 0; seg[n]+=lazy[n]*(r-l+1); if(l!=r) { lazy[2*n]+=lazy[n]; lazy[2*n+1]+=lazy[n]; } lazy[n]=0; if(l==r) return seg[n]; return sg(2*n,l,mid,i)+sg(2*n+1,mid+1,r,i); } void su(ll n , ll l , ll r , ll l1 , ll r1 , ll x) { if(l>r1||r<l1) return; if(l>=l1&&r<=r1) { lazy[n]+=x; return; } su(2*n,l,mid,l1,r1,x); su(2*n+1,mid+1,r,l1,r1,x); } int main() { d3 ll n , q , s , t; cin >> n >> q >> s >> t; for(int i = 0 ; n>=i ; i++) cin >> a[i]; sb(1,0,n); ll ans = 0; for(int i = 0 ; n>i ; i++) { ll ans1 = a[i]-a[i+1]; if(a[i]<a[i+1]) ans1*=s; else ans1*=t; ans+=ans1; } while(q--) { ll l , r , x; cin >> l >> r >> x; if(l) { ll x1 = sg(1,0,n,l-1); ll x2 = sg(1,0,n,l); ll ans1 = x1-x2; if(x1<x2) ans1*=s; else ans1*=t; ans-=ans1; } if(r<n) { ll x1 = sg(1,0,n,r); ll x2 = sg(1,0,n,r+1); ll ans1 = x1-x2; if(x1<x2) ans1*=s; else ans1*=t; ans-=ans1; } su(1,0,n,l,r,x); if(l) { ll x1 = sg(1,0,n,l-1); ll x2 = sg(1,0,n,l); ll ans1 = x1-x2; if(x1<x2) ans1*=s; else ans1*=t; ans+=ans1; } if(r<n) { ll x1 = sg(1,0,n,r); ll x2 = sg(1,0,n,r+1); ll ans1 = x1-x2; if(x1<x2) ans1*=s; else ans1*=t; ans+=ans1; } cans } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...