제출 #232825

#제출 시각아이디문제언어결과실행 시간메모리
232825palpatinezwFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
160 ms14072 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int N, Q, S, T; int a[200005], fw[2][200005]; void update(int x, int v, int fwn) { //v is value, x is position for (;x <=N; x+=x&(-x)) fw[fwn][x] += v; } int sum(int x, int fwn) { int res = 0; for(; x; x-=x&(-x)) res += fw[fwn][x]; return res; } int rs(int x, int y, int fwn) { return sum(y, fwn) - sum(x-1, fwn); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> Q >> S >> T; for (int i = 0; i <= N; i++) { cin >> a[i]; } for (int i = N; i > 0; i--) { a[i] -= a[i-1]; if (a[i] > 0) { update(i, a[i], 0); } else if (a[i] < 0) { update(i, a[i], 1); } } while (Q--) { int l, r, x; cin >> l >> r >> x; r++; int nl = a[l] + x; if (nl > 0) { if (a[l] > 0) { update(l, x, 0); } else { update(l, -1 * a[l], 1); update(l, nl, 0); } } else { if (a[l] < 0) { update(l, x, 1); } else { update(l, -1 * a[l], 0); update(l, nl, 1); } } //~ printf("At pos %d, %d updated to %d\n", l, a[l], nl); a[l] = nl; x *= -1; if (r > N) { int ret = (sum(N, 1) * T * -1) - (sum(N, 0) * S); cout << ret << '\n'; continue; } int nr = a[r] + x; if (nr > 0) { if (a[r] > 0) { update(r, x, 0); } else { update(r, -1 * a[r], 1); update(r, nr, 0); } } else { if (a[r] < 0) { update(r, x, 1); } else { update(r, -1 * a[r], 0); update(r, nr, 1); } } //~ printf("At pos %d, %d updated to %d\n", r, a[r], nr); a[r] = nr; //~ printf("Total incs: %d, Total decs: %d\nList: ", sum(N, 0), sum(N, 1)); //~ int cur = 0; //~ for (int i = 1; i <= N; i++) { //~ cout << cur + a[i] << ' '; //~ cur += a[i]; //~ } //~ cout << '\n'; int ret = (sum(N, 1) * T * -1) - (sum(N, 0) * S); cout << ret << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...