제출 #981132

#제출 시각아이디문제언어결과실행 시간메모리
981132ShaShiFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
294 ms23244 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define F first #define S second #define kill(x) cout << x << endl, exit(0); #define endl "\n" using namespace std; typedef long long ll; typedef long double ld; const int MAXN = (int)1e6 + 7; const int MOD = (int)1e9 + 7; const ll INF = (ll)1e18 + 7; int n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag; int arr[MAXN], A, B, U, D; /* Segment Tree */ #define mid ((l+r)>>1) #define lid (id<<1) #define rid (lid|1) int seg[MAXN<<2], lazy[MAXN<<2]; inline void relax(int l, int r, int id) { if (lazy[id] == 0) return; seg[lid] += lazy[id]; seg[rid] += lazy[id]; lazy[lid] += lazy[id]; lazy[rid] += lazy[id]; lazy[id] = 0; } void build(int l=0, int r=n, int id=1) { if (l+1 == r) { seg[id] = arr[l]; return; } build(l, mid, lid); build(mid, r, rid); seg[id] = seg[lid]+seg[rid]; } void upd(int s, int t, int x, int l=0, int r=n, int id=1) { if (s >= t) return; if (s <= l && t >= r) { seg[id] += x; lazy[id] += x; return; } relax(l, r, id); if (s < mid) upd(s, t, x, l, mid, lid); if (t > mid) upd(s, t, x, mid, r, rid); seg[id] = seg[lid]+seg[rid]; } int get(int x, int l=0, int r=n, int id=1) { if (l+1 == r) return seg[id]; relax(l, r, id); if (x < mid) return get(x, l, mid, lid); return get(x, mid, r, rid); } /* Segment Tree */ inline void f(int u, int v, int x) { if (u < v) U += (v-u)*x; else D += (u-v)*x; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q >> A >> B; n++; for (int i=0; i<n; i++) { cin >> arr[i]; if (i) f(arr[i-1], arr[i], 1); } build(); while (q--) { cin >> u >> v >> w; f(get(u-1), get(u), -1); if (v != n-1) f(get(v), get(v+1), -1); upd(u, v+1, w); f(get(u-1), get(u), 1); if (v != n-1) f(get(v), get(v+1), 1); // cout << "!"; cout << D*B-U*A << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...