Submission #245272

#TimeUsernameProblemLanguageResultExecution timeMemory
245272WhaleVomitFoehn Phenomena (JOI17_foehn_phenomena)C++14
30 / 100
1086 ms22456 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back #define mp make_pair #define all(v) v.begin(), v.end() #define sz(v) (int)v.size() #define MOO(i, a, b) for(int i=a; i<b; i++) #define M00(i, a) for(int i=0; i<a; i++) #define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--) #define M00d(i,a) for(int i = (a)-1; i>=0; i--) #define FAST ios::sync_with_stdio(0); cin.tie(0); #define finish(x) return cout << x << '\n', 0; #define dbg(x) cerr << ">>> " << #x << " = " << x << "\n"; #define _ << " _ " << typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int,int> pi; typedef pair<ld,ld> pd; typedef complex<ld> cd; template<class T> struct node { T val; T lazy; int l, r; node* left; node* right; node(int l, int r) { this -> l = l; this -> r = r; this -> left = nullptr; this -> right = nullptr; } }; template<class T, int SZ> struct segtree { // modify these T combIdentity = 0; T comb(T l, T r) { return l+r; } T pushIdentity = 0; void push(node<T>* n) { n->val += n->lazy*(n->r - n->l + 1); if(n->l != n->r) { n->left->lazy += n->lazy; n->right->lazy += n->lazy; } n->lazy = pushIdentity; } node<T>* root; segtree() { int ub = 1; while(ub < SZ) ub *= 2; root = new node<T>(0, ub-1); root->val = pushIdentity; root->lazy = pushIdentity; } void propagate(node<T>* n) { if(n->l != n->r) { int mid = ((n->l) + (n->r))/2; if(n->left == nullptr) { n->left = new node<T>(n->l, mid); n->left->val = pushIdentity; n->left->lazy = pushIdentity; } if(n->right == nullptr) { n->right = new node<T>(mid+1, n->r); n->right->val = pushIdentity; n->right->lazy = pushIdentity; } } push(n); } void updN(node<T>* n, int i1, int i2, T val) { propagate(n); if(i2 < n->l || i1 > n->r) return; if(i1 <= n->l && i2 >= n->r) { n->lazy = val; push(n); return; } updN(n->left, i1, i2, val); updN(n->right, i1, i2, val); n->val = comb(n->left->val, n->right->val); } void upd(int i1, int i2, T val) { updN(root, i1, i2, val); } T queryN(node<T>* n, int i1, int i2) { propagate(n); if(i2 < n->l || i1 > n->r) return combIdentity; if(n->l >= i1 && n->r <= i2) return n->val; T a = combIdentity; if(n->left != nullptr) a = comb(a, queryN(n->left, i1, i2)); if(n->right != nullptr) a = comb(a, queryN(n->right, i1, i2)); return a; } T query(int i1, int i2) { return queryN(root, i1, i2); } }; const int MAX_N = 200200; segtree<ll,MAX_N> st; ll S, T; ll get(int i) { ll x1 = st.query(i,i); ll x2 = st.query(i+1,i+1); if(x1 < x2) return -S*(x2-x1); else return T*(x1-x2); } int main() { FAST int n, q; cin >> n >> q >> S >> T; n++; vector<ll> arr(n); M00(i, n) cin >> arr[i]; M00(i, n) st.upd(i, i, arr[i]); ll ans = 0; M00(i, n-1) ans += get(i); M00(i, q) { int l, r, x; cin >> l >> r >> x; if(l != 0) ans -= get(l-1); if(r != n-1) ans -= get(r); st.upd(l,r,x); if(l != 0) ans += get(l-1); if(r != n-1) ans += get(r); cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...