Submission #1198470

#TimeUsernameProblemLanguageResultExecution timeMemory
1198470PlayVoltzFoehn Phenomena (JOI17_foehn_phenomena)C++20
100 / 100
602 ms30764 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second struct node{ int s, e, m, val, lazy; node *l, *r; void create(){ if (l==nullptr){ l = new node(s, m); r = new node(m+1, e); } } void propagate(){ val+=lazy*(e-s+1); if (s!=e){ create(); l->lazy+=lazy; r->lazy+=lazy; } lazy=0; } node(int S, int E){ s = S, e = E, m = (s+e)/2; val=lazy=0; l=r=nullptr; } void up(int left, int right, int v){ propagate(); if (s==left && e==right)lazy+=v; else{ create(); if (right<=m)l->up(left, right, v); else if (left>m)r->up(left, right, v); else l->up(left, m, v), r->up(m+1, right, v); r->propagate(), l->propagate(); val=l->val+r->val; } } int query(int left, int right){ propagate(); if (s==left && e==right)return val; create(); if (right<=m)return l->query(left, right); else if (left>m)return r->query(left, right); else return l->query(left, m)+r->query(m+1, right); } }*st; int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q, s, t, a, b, c, ans=0; cin>>n>>q>>s>>t; vector<int> vect(n+1); st = new node(0, n); for (int i=0; i<=n; ++i){ cin>>vect[i]; st->up(i, i, vect[i]); if (i){ if (vect[i-1]<vect[i])ans-=(vect[i]-vect[i-1])*s; else ans+=(vect[i-1]-vect[i])*t; } } while (q--){ cin>>a>>b>>c; int lp = st->query(a-1, a-1), l=st->query(a, a), r=st->query(b, b), rp=LLONG_MIN/2; if (b!=n)rp=st->query(b+1, b+1); if (c>0){ ans-=min(c, max(0ll, lp-l))*t; ans-=(c-min(c, max(0ll, lp-l)))*s; if (rp!=LLONG_MIN/2){ ans+=min(c, max(0ll, rp-r))*s; ans+=(c-min(c, max(0ll, rp-r)))*t; } } else{ ans+=min(-c, max(0ll, l-lp))*s; ans+=(-c-min(-c, max(0ll, l-lp)))*t; if (rp!=LLONG_MIN/2){ ans-=min(-c, max(0ll, r-rp))*t; ans-=(-c-min(-c, max(0ll, r-rp)))*s; } } st->up(a, b, c); cout<<ans<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...