제출 #231628

#제출 시각아이디문제언어결과실행 시간메모리
231628peijarFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
240 ms19932 KiB
#include <bits/stdc++.h> using namespace std; #define SZ(v) ((int)(v).size()) using ll = long long; template<class T> struct Segtree_rangeAdd_pointQuery { int nb_elem; int LIM; vector<T> seg; int deb; Segtree_rangeAdd_pointQuery(int N) { nb_elem = 1; while (nb_elem < N) nb_elem *= 2; LIM = 4 * nb_elem; deb = nb_elem-1; seg.resize(LIM); } Segtree_rangeAdd_pointQuery(vector<T> arr) { *this = Segtree_rangeAdd_pointQuery(SZ(arr)); for (int i(0); i < SZ(arr); ++i) seg[deb + i] = arr[i]; } void add(int lo, int up, T delta) { lo += deb; up += deb; while (lo < up) { if (up%2) seg[up] += delta; if (lo%2==0) seg[lo] += delta; lo /= 2; up = (up-2)/2; } if (lo == up) seg[lo] += delta; } T query(int id) { id += deb; T ans(seg[id]); while (id) { id = (id-1)/2; ans += seg[id]; } return ans; } }; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll nb_elem, nb_requetes, up, down; cin >> nb_elem >> nb_requetes >> up >> down; vector<ll> arr(nb_elem+1); for (auto &v : arr) cin >> v; Segtree_rangeAdd_pointQuery<ll> seg = Segtree_rangeAdd_pointQuery<ll>(arr); ll temp(0); auto find_delta = [&](ll a, ll b) { if (a >= b) return -down * (b - a); else return -up * (b-a); }; for (int i(0); i < nb_elem; ++i) temp += find_delta(arr[i], arr[i+1]); while (nb_requetes--) { ll L, R, delta; cin >> L >> R >> delta; ll u1 = seg.query(L-1); ll u2 = seg.query(L); ll v1 = seg.query(R); ll v2 = (R < nb_elem ? seg.query(R+1) : v1); temp -= find_delta(u1, u2); temp -= find_delta(v1, v2); seg.add(L, R, delta); u2 = seg.query(L); v1 = seg.query(R); temp += find_delta(u1, u2); if (R < nb_elem) temp += find_delta(v1, v2); cout << temp << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...