제출 #670449

#제출 시각아이디문제언어결과실행 시간메모리
670449radalFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
382 ms8952 KiB
#include <bits/stdc++.h> #pragma GCC target("sse,sse2,avx2") #pragma GCC optimize("unroll-loops,O2") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef pair<int,int> pll; constexpr int N = 2e5+10,mod = 1e9+7,maxm = 210; constexpr ll inf = 1e9+10; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; // if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k >>= 1; } return z; } ll seg[N*4]; int a[N]; void upd(int l,int r,int s,int e,int x,int v = 1){ if (s <= l && r <= e){ seg[v] += x; return; } if (s >= r || l >= e) return; int m = (l+r) >> 1,u = (v << 1); upd(l,m,s,e,x,u); upd(m,r,s,e,x,u|1); } ll que(int l,int r,int p,int v = 1){ if (r-l == 1) return seg[v]; int m = (l+r) >> 1,u = (v << 1); if (p < m) return que(l,m,p,u)+seg[v]; return que(m,r,p,u|1)+seg[v]; } int main(){ ios :: sync_with_stdio(0); cin.tie(0); int n,q,s,t; cin >> n >> q >> s >> t; ll cnt1 = 0,cnt2 = 0; s *= -1; rep(i,0,n+1){ cin >> a[i]; if (i && a[i] > a[i-1]) cnt1 += a[i]-a[i-1]; else if (i) cnt2 += a[i-1]-a[i]; upd(0,n+1,i,i+1,a[i]); } while (q--){ int l,r,h; cin >> l >> r >> h; ll x = que(0,n+1,l),y = que(0,n+1,l-1); if (x > y) cnt1 -= (x-y); else cnt2 -= (y-x); if (r < n){ x = que(0,n+1,r),y = que(0,n+1,r+1); if (x < y) cnt1 -= (y-x); else cnt2 -= (x-y); } upd(0,n+1,l,r+1,h); x = que(0,n+1,l),y = que(0,n+1,l-1); if (x > y) cnt1 += (x-y); else cnt2 += (y-x); if (r < n){ x = que(0,n+1,r),y = que(0,n+1,r+1); if (x < y) cnt1 += (y-x); else cnt2 += (x-y); } cout << 1ll*cnt1*s+1ll*cnt2*t << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...