제출 #1119412

#제출 시각아이디문제언어결과실행 시간메모리
1119412vjudge1Foehn Phenomena (JOI17_foehn_phenomena)C++17
0 / 100
79 ms52900 KiB
#include <bits/stdc++.h> #define F first #define S second #define LL long long #define rep(i, x) for(auto &i : (x)) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define left(x) ((x)<<1) #define right(x) ((x)>>1) #define LSOne(x) (x & -(x)) using namespace std; using T = pair<pair<int, int>, int>; const int SZ = 2e5 + 1; const LL MOD = 1e9 + 7; const LL INF = 1e18 + 1; LL bp (LL b, LL e, LL m = MOD) { if ( e == 0 ) return 1; LL T = bp(b, e / 2); T *= T; T %= m; if ( e & 1 ) T *= b; return T %= m; } LL nv_i (LL a) { return bp(a, MOD - 2); }; LL gcd (LL a, LL b) { return (b == 0 ? a : gcd(b, a % b)); } LL lcm(LL a, LL b) { return (a * (b / gcd(a, b))); } LL ceil (LL a, LL b) { return ((a + b - 1) / b); } struct FTree { int n; vector<LL> FT; FTree(int _n) { n = _n; FT.resize(n + 1); } void update(int pos, LL val) { for(; pos <= n; pos += LSOne(pos)) { FT[pos] += val; } } LL query(int pos) { LL sum = 0; for(; pos > 0; pos -= LSOne(pos)) { sum += FT[pos]; } return sum; } LL query(int L, int R) { return query(R) - query(L - 1); } }; void solve() { int n, q; LL s, t; cin >> n >> q >> s >> t; vector<LL> V(4*n + 2), DIF(4*n + 2); for(int i = 0; i < n; i ++) cin >> V[i]; FTree FTree_0(4*n + 2), FTree_1(4*n + 2); for(int i = 0; i < n - 1; i ++) { LL dif = V[i] - V[i + 1]; if(dif <= 0) FTree_0.update(i + 1, dif); else FTree_1.update(i + 1, dif); } for(int i = 0; i < q; i ++) { int L, R; LL val; cin >> L >> R >> val; if(L == R) { V[L] += val; } else { V[L] += val; V[R] += val; } LL dif_L = V[L - 1] - V[L], dif_R = V[R] - V[R + 1]; LL sum_0_L = FTree_0.query(L, L); LL sum_0_R = FTree_0.query(R + 1, R + 1); LL sum_1_L = FTree_1.query(L, L); LL sum_1_R = FTree_1.query(R + 1, R + 1); if(dif_L <= 0) { FTree_1.update(L, -sum_1_L); FTree_0.update(L, -sum_0_L); FTree_0.update(L, dif_L); } else { FTree_0.update(L, -sum_0_L); FTree_1.update(L, -sum_1_L); FTree_1.update(L, dif_L); } if(dif_R <= 0) { FTree_1.update(R + 1, -sum_1_R); FTree_0.update(R + 1, -sum_0_R); FTree_0.update(R + 1, dif_R); } else { FTree_0.update(R + 1, -sum_0_R); FTree_1.update(R + 1, -sum_1_R); FTree_1.update(R + 1, dif_R); } cout << FTree_0.query(n - 1) * s + FTree_1.query(n - 1) * t << "\n"; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...