제출 #864379

#제출 시각아이디문제언어결과실행 시간메모리
864379dsyzFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
420 ms36736 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define MAXN (1000005) struct node{ ll s, e, m, val, lazy; node *l, *r; node(ll S, ll E){ s = S, e = E, m = (s+e)/2; val = 0; lazy = 0; if(s != e){ l = new node(s,m); r = new node(m + 1,e); } } void propogate(){ if(lazy==0) return; val += lazy*(e-s+1); if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement) l->lazy += lazy; r->lazy += lazy; } lazy = 0; } void update(ll S, ll E, ll V){ propogate(); if(s == S && e == E) lazy += V; else{ if(E <= m) l->update(S, E, V); else if (m < S) r->update(S, E, V); else l->update(S, m, V),r->update(m+1, E, V); l->propogate(),r->propogate(); val = l->val + r->val; } } ll query(ll S, ll E){ propogate(); //remember to propogate if(s == S && e == E) return val; else if(E <= m) return l->query(S, E); else if(S >= m+1) return r->query(S, E); else return l->query(S, m) + r->query(m+1, E); } } *root; int main(){ ios_base::sync_with_stdio(false);cin.tie(0); ll N,Q,S,T; cin>>N>>Q>>S>>T; root = new node(0,N + 5); ll A[N + 1]; for(ll i = 0;i <= N;i++){ cin>>A[i]; root -> update(i,i,A[i]); } ll temperature = 0; for(ll i = 0;i < N;i++){ if(A[i] < A[i + 1]) temperature -= abs(A[i + 1] - A[i]) * S; else temperature += abs(A[i] - A[i + 1]) * T; } for(ll q = 0;q < Q;q++){ ll L,R,X; cin>>L>>R>>X; if(L > 0){ ll A1 = root -> query(L - 1,L - 1); ll A2 = root -> query(L,L); if(A1 < A2) temperature += abs(A2 - A1) * S; else temperature -= abs(A1 - A2) * T; if(A1 < A2 + X) temperature -= abs((A2 + X) - A1) * S; else temperature += abs(A1 - (A2 + X)) * T; } if(R < N){ ll A1 = root -> query(R,R); ll A2 = root -> query(R + 1,R + 1); if(A1 < A2) temperature += abs(A2 - A1) * S; else temperature -= abs(A1 - A2) * T; if(A1 + X < A2) temperature -= abs(A2 - (A1 + X)) * S; else temperature += abs((A1 + X) - A2) * T; } root -> update(L,R,X); cout<<temperature<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...