Submission #232825

#	Time	Username	Problem	Language	Result	Execution time	Memory
232825		palpatinezw	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	160 ms	14072 KiB

foehn_phenomena

#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';
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60