제출 #854580

#제출 시각아이디문제언어결과실행 시간메모리
854580BrineTwFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
116 ms7344 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> #define debug(x) cerr << #x << ' ' << x << '\n' #define endl '\n' using namespace std; const int M = 1e9 + 7; typedef long long ll; struct BIT { int N; vector<ll> v; BIT(int N): N(N + 1), v(N + 2) {} inline int lb(int x) { return x & -x; } void update(int i, ll dx) { for (; i <= N; i += lb(i)) v[i] += dx; } ll query(int i) { ll ans = 0; for (; i; i -= lb(i)) ans += v[i]; return ans; } }; int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int N, Q, S, T; cin >> N >> Q >> S >> T; vector<ll> h(N + 1); for (auto& n: h) cin >> n; BIT bit(N); ll current = 0; for (int i = 1; i <= N; i++) { if (h[i] > h[i - 1]) { current -= (h[i] - h[i - 1]) * S; } else { current -= (h[i] - h[i - 1]) * T; } bit.update(i, h[i] - h[i - 1]); } // for (auto& n: bit.v) cerr << n << " \n"[&n == &bit.v.back()]; for (int i = 0; i <= N; i++) { // cerr << bit.query(i) << ' '; } // cerr << '\n'; ll l, r, dy; for (int i = 0; i < Q; i++) { cin >> l >> r >> dy; ll h1, h2, h3, h4; h1 = bit.query(l - 1); h2 = bit.query(l); h3 = bit.query(r); h4 = bit.query(r + 1); if (h2 > h1) { current += (h2 - h1) * S; } else { current += (h2 - h1) * T; } if (r != N && h4 > h3) { current += (h4 - h3) * S; } else if (r != N && h4 <= h3) { current += (h4 - h3) * T; } bit.update(l, dy); bit.update(r + 1, -dy); h1 = bit.query(l - 1); h2 = bit.query(l); h3 = bit.query(r); h4 = bit.query(r + 1); current -= (h2 > h1 ? S : T) * (h2 - h1); if (r != N) current -= (h4 > h3 ? S : T) * (h4 - h3); cout << current << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...