Submission #733434

#	Time	Username	Problem	Language	Result	Execution time	Memory
733434		shoryu386	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	651 ms	14648 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define N 200010
int fw[N], fw2[N];
void update(int x, int y, int v) { //inclusive
	x++; y++;
    for (int tx=x; tx < N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
    for (int ty=y+1; ty < N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
}
int sum (int x) {
	x++;
    int res = 0;
    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
    return res;
}
inline int range_sum(int x, int y) { //inclusive
    return sum(y)-sum(x-1);
}

signed main() {
  int n, q, s, t;
  cin >> n >> q >> s >> t;

  int h[n+1];
  for (int x = 0; x < n+1; x++) {cin >> h[x]; if (x != 0) update(x, x, h[x]);}
  int ans = 0;
  for (int x = 0; x < n; x++){
    if (h[x] < h[x+1]) ans -= s * (h[x+1] - h[x]);
    else ans += t * (h[x] - h[x+1]);
  }
  
  for (int x = 0; x < q; x++){
	int a, b, c;
	cin >> a >> b >> c; //bruh wtf need fenwick, cri
	
	//reset to fresh
	
	if (range_sum(a-1, a-1) < range_sum(a, a)){
		ans += s * (range_sum(a, a) - range_sum(a-1, a-1));
	}
	else{
		ans -= t * (range_sum(a-1, a-1) - range_sum(a, a));
	}

	if (b != n && range_sum(b, b) < range_sum(b+1, b+1)){
		ans += s * (range_sum(b+1, b+1) - range_sum(b, b));
	}
	else if (b != n){
		ans -= t * (range_sum(b, b) - range_sum(b+1, b+1));
	}
	
	update(a, b, c);
	
	if (range_sum(a-1, a-1) < range_sum(a, a)){
		ans -= s * (range_sum(a, a) - range_sum(a-1, a-1));
	}
	else{
		ans += t * (range_sum(a-1, a-1) - range_sum(a, a));
	}

	if (b != n && range_sum(b, b) < range_sum(b+1, b+1)){
		ans -= s * (range_sum(b+1, b+1) - range_sum(b, b));
	}
	else if (b != n){
		ans += t * (range_sum(b, b) - range_sum(b+1, b+1));
	}
	
	cout << ans << '\n';
  }
}

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