제출 #753623

#제출 시각아이디문제언어결과실행 시간메모리
753623ByeWorldFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
989 ms19832 KiB
#include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define ll long long #define int long long using namespace std; typedef pair<int,int> pii; typedef pair<int, pii> ipii; const int MAXN = 2e5+10; const int INF = 1e9; const int MOD = 1e9+7; int n, q, s, t; int a[MAXN]; int up, dw; int st[4*MAXN], laz[4*MAXN]; int bd(int id, int l, int r){ if(l==r) return st[id] = a[l]; return st[id] = bd(2*id, l, (l+r)/2) + bd(2*id+1, (l+r)/2+1, r); } void bnc(int id){ if(laz[id] == 0) return; laz[2*id] += laz[id]; st[2*id] += laz[id]; laz[2*id+1] += laz[id]; st[2*id+1] += laz[id]; laz[id] = 0; } int que(int id, int l, int r, int x){ if(r<x || x<l) return 0; if(l==r && l==x) return st[id]; bnc(id); return que(2*id, l, (l+r)/2, x) + que(2*id+1, (l+r)/2+1, r, x); } int upd(int id, int l, int r, int x, int y, int p){ if(r<x || y<l) return st[id]; if(x<=l && r<=y){ laz[id] += p; return st[id] += p; } bnc(id); return st[id] = upd(2*id, l, (l+r)/2, x, y, p) + upd(2*id+1, (l+r)/2+1, r, x, y, p); } signed main(){ //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> q >> s >> t; for(int i=0; i<=n; i++) cin >> a[i]; for(int i=1; i<=n; i++){ int te = a[i]-a[i-1]; if(te < 0) dw += te; else up += te; } bd(1, 1, n); for(int i=1; i<=q; i++){ int l, r, p; cin >> l >> r >> p; int al = que(1, 1, n, l); int al1 = que(1, 1, n, l-1); int te = al-al1; if(te < 0) dw -= te; else up -= te; if(r!=n){ int ar = que(1, 1, n, r); int ar1 = que(1, 1, n, r+1); te = ar1-ar; if(te < 0) dw -= te; else up -= te; } upd(1, 1, n, l, r, p); //cout << al << ' ' << al1 << ' ' << ar1 << ' '<< ar << "ar\n"; al = que(1, 1, n, l); te = al-al1; if(te < 0) dw += te; else up += te; if(r!=n){ int ar = que(1, 1, n, r); int ar1 = que(1, 1, n, r+1); te = ar1-ar; if(te < 0) dw += te; else up += te; } //cout << dw << ' ' << up << "dw\n"; cout << dw*(-t) + up*(-s) << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...