제출 #539210

#제출 시각아이디문제언어결과실행 시간메모리
539210timreizinFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
155 ms14636 KiB
#include <iostream> #include <vector> #include <algorithm> #include <deque> #include <cassert> #include <numeric> using namespace std; using ll = long long; struct BIT { int n; vector<ll> tree; void update(int p, ll val) { for (;p < n; p |= p + 1) tree[p] += val; } BIT(vector<ll> a) : n((int)a.size()) { tree.resize(n); for (int i = 0; i < n; ++i) update(i, a[i]); } ll get() { ll res = 0; for (int i = n - 1; i >= 0; i = (i & (i + 1)) - 1) res += tree[i]; return res; } }; int main() { cin.tie(0)->sync_with_stdio(0); int n, q; ll s, t; cin >> n >> q >> s >> t; vector<ll> a(n); cin >> a.front(); for (ll &i : a) cin >> i; adjacent_difference(a.begin(), a.end(), a.begin()); vector<ll> help = a; for (ll &i : help) { if (i < 0) i *= -t; else i *= -s; } BIT st(help); while (q--) { int l, r; ll x; cin >> l >> r >> x; //l - 1 //r a[l - 1] += x; ll next = a[l - 1] * (a[l - 1] < 0 ? -t : -s); st.update(l - 1, next - help[l - 1]); help[l - 1] = next; if (r != n) { a[r] -= x; ll next = a[r] * (a[r] < 0 ? -t : -s); st.update(r, next - help[r]); help[r] = next; } cout << st.get() << '\n'; } return 0; } /* 3 5 1 2 0 4 1 8 1 2 2 1 1 -2 2 3 5 1 2 -1 1 3 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...